数字游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1201 字

求[a,b]中从左到右各位数字单调不降的正整

一本通
例

正文

/*
原题：数字游戏（一本通 5.3 例 2，不降数）
题意：求 [a,b] 中从左到右各位数字单调不降（后一位 ≥ 前一位）的正整数个数，多组询问。
思路：数位 DP，state=(pos,last,started,tight)。
     未开始时放 0 仍为前导零；一旦放非 0 数字则开始，其后每位必须 ≥ 上一位。
     答案 = f(b) - f(a-1)，f 统计 [0,n] 中的不降正整数。
复杂度：时间 O(log10 b * 10)，空间 O(log10 b * 10)
易错点：前导零不能当作“数字”参与比较；单数字一律算不降数。
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dig[15];
ll memo[15][10][2][2];
int len;
ll dfs(int pos, int last, bool started, bool tight){
    if(pos == len){
        return started ? 1 : 0;
    }
    if(memo[pos][last][started][tight] != -1) return memo[pos][last][started][tight];
    ll ans = 0;
    int up = tight ? dig[pos] : 9;
    for(int d = 0; d <= up; d++){
        if(started && d < last) continue;
        ans += dfs(pos + 1, d, started || d != 0, tight && d == up);
    }
    return memo[pos][last][started][tight] = ans;
}
ll f(ll n){
    len = 0;
    ll t = n;
    while(t){
        dig[len++] = t % 10;
        t /= 10;
    }
    if(len == 0) dig[len++] = 0;
    reverse(dig, dig + len);
    memset(memo, -1, sizeof(memo));
    return dfs(0, 0, false, true);
}
int main(){
    ll a, b;
    while(cin >> a >> b){
        cout << f(b) - f(a - 1) << "\n";
    }
    return 0;
}

数字游戏

正文

一本通·提高篇的其它内容