1082. 数字游戏 (数位DP)

题目链接：点此跳转

题目大意：
科协里最近很流行数字游戏。

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

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

输入格式
输入包含多组测试数据。

每组数据占一行，包含两个整数 a 和 b。

输出格式
每行给出一组测试数据的答案，即 [a,b] 之间有多少不降数。

数据范围
1≤ a ≤ b ≤2³¹?1

解题思路：
f[i][j] 数组代表着最高位是j并且一共有i位不降数的集合
f[i][j] = f[i-1][j] + f[i-1][j+1] + f[i-1][j+2] +…+ f[i-1][9];

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

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

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

Code:

#include<iostream>
#include<vector>
using namespace std;
const int maxn=30;int f[maxn][maxn];void init(){
              //预处理f数组for(int i=0;i<=9;i++) f[1][i]=1;for(int i=2;i<maxn;i++){
    for(int j=0;j<=9;j++){
    for(int k=j;k<=9;k++){
    f[i][j]+=f[i-1][k];}}}
}int solve(int n){
    if(!n) return 1;vector<int> nums;while(n) nums.push_back(n%10),n/=10;int res=0;int last=0;for(int i=nums.size()-1;i>=0;i--){
    int x=nums[i];for(int j=last;j<x;j++){
    res+=f[i+1][j];  //(0~i位，一共有i+1位)}if(x<last) break;last=x;if(!i) res++; }return res;
}int main(){
    init();int a,b;while(~scanf("%d%d",&a,&b)){
    printf("%d\n",solve(b)-solve(a-1));}}