题目描述

科协里最近很流行数字游戏。

某人命名了一种不降数，这种数字必须满足从左到右各位数字呈非下降关系，如 123，446。

现在大家决定玩一个游戏，指定一个整数闭区间 [a,b]，问这个区间内有多少个不降数。

样例

输入
1 9
1 19
输出
9
18

数据范围

$1≤a≤b≤2^{31}−1$

数位DP

按照数位DP分析步骤： 假设我们当前枚举到第i位，且第i位上的数字是x，那么现在对于答案的第i位数字j来说，可以填两类数字：

• 1.j取0~x-1
  那么res += f[i+1][j];

• 2.j取x
  last记录x，再枚举下一位

f数组

f[i][j] 表示一共有i位，且最高位数字为j的不降数的个数
状态转移： 因为最高位已经固定，所以假设第i-1位是k，根据不降数定义k>=j,所以

$f[i][j] = \sum_{k=j}^{9}f[i-1][k]$

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12;
int f[N][N];  //f[i][j] 表示最高位是j且一共有i位的不降数的个数

void init(){
    for(int i = 0; i<=9; i++) f[1][i] = 1;
    for(int i = 2; i<=N; i++){
        for(int j = 0; j<=9; j++)
            for(int k = j; k<=9; k++)
                f[i][j] += f[i-1][k]; //f[i][j] = f[i-1][j] + f[i-1][j+1] + f[i-1][j+2] +...+ f[i-1][9];
    }
}

int dp(int n){
    if(!n) return 1;
    int res = 0,last = 0;

    vector<int> a;
    while(n) a.push_back(n%10),n/=10;
    int len = a.size()-1;

    for(int i = len; i>=0; --i){  //从高到低枚举
        int x = a[i];
        for(int j = last; j<x; j++)//last表示上一位数字大小,当前枚举的数字不能比last小(不降数定义)
            res += f[i+1][j]; //(0~i位，一共有i+1位)

        if(x<last) break;  //若小，则break
        last = x;  //更新last

        if(!i) res++;
    }
    return res;
}
int main()
{
    init();
    int l,r;
    while(cin>>l>>r) cout<<dp(r) - dp(l-1)<<endl;;
    return 0;
}