题目：数字游戏

1082. 数字游戏 - AcWing题库

分析：

前缀和思想: dp(m) - dp(n-1)

用树的角度分析。

比最高位小的， 左分支讨论，等于最高位的进入右分支，（同时进入右分支有条件，就是当前位最大值last <= x(下一位值，此高位）.

对于左分支，随便弄，只要后面的大于前面的就行（不会超过n的值）=>这个东西提前算好了，就是f[i][j] i位数，最高位是j，这种情况下满足性质有几位。

符合条件进入右分支。

如果能枚举完，还要加上特殊情况（ans ++);

代码:

#include<bits/stdc++.h>
using namespace std;const int N = 20;
int f[N][N];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]; // 下一位>=j的全加起来
}int dp(int n) {// 特判n == 0,只有0这一种情况，因为n=0 后面循环无法通过存储numsif(!n) return 1;vector<int> nums;while(n) nums.push_back(n%10), n/=10;int ans = 0, last = 0; // 存上一个最大值for(int i = nums.size()-1; i >=0; i --) {int x = nums[i];// 进入右分支条件： x >= last// j >= lastfor(int j = last; j < x; j ++) {ans += f[i+1][j];}if(last>x) break;last = x;// 右子树进入到最后一个右分支，特殊处理（算一种情况）if(!i) ans ++;}return ans;
}int main() {int n, m;init();while(cin >> n >> m) cout << dp(m) - dp(n-1) << endl;return 0;
}