E36 数位DP 数字游戏

#include<bits/stdc++.h> 
using namespace std;
const int N=20;
int f[N][15], a[N]; //f[i][j]表示位数为i，最高位的数是j的不降数的个数
int calc(int x){ //计算[0, x]区间内的不降数
    if(x==0) return 1;  //0也是不降数
    int len=0, last=0, ans=0; //last是上一位的数（更高位
    while(x>0) a[++len]=x%10, x/=10;
    for(int i=len; i>=1; i--){
        for(int j=last; j<a[i]; j++) 
        //<a[i]是因为这样才能保证枚举的数不超过x
            ans+=f[i][j];   
        if(last>a[i]) break; //再往后计算的数就不是不降数了
        last=a[i];
        if(i==1) ans++; //x本身就是不降数
    }
    return ans;
}
int main(){
    //freopen("a.in", "r", stdin);
    int a, b; 
    memset(f, 0, sizeof(f));
    for(int i=0; i<=9; i++) f[1][i]=1;
    for(int t=2; t<=15; t++){ //枚举位数
        for(int i=0; i<=9; i++){
            for(int j=i; j<=9; j++)
                f[t][i]+=f[t-1][j]; 
            //当前个位数为i，位数为t加上个位数为j，位数为t-1的不降数
            //（其实相当于接后面
        }
    }
    while(scanf("%d%d", &a, &b)!=EOF){
        printf("%d\n", calc(b)-calc(a-1)); //求区间
    }
    return 0;
}