AcWing 1082. 数字游戏
原题链接
中等
作者:
炽热的
,
2023-03-14 23:33:23
,
所有人可见
,
阅读 130
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int len;
int nums[N], f[N][N];
int dfs(int pos, int pre, int limit) {
if (!pos) return 1;
if (!limit && ~f[pos][pre]) return f[pos][pre];
int up = limit ? nums[pos] : 9, res = 0;
for (int i = 0; i <= up; i ++ )
if (i >= pre) res += dfs(pos - 1, i, limit && i == up);
return limit ? res : f[pos][pre] = res;
}
int calc(int x) {
len = 0;
memset(f, -1, sizeof f);
while (x) nums[ ++ len] = x % 10, x /= 10;
return dfs(len, 0, 1);
}
int main() {
int l, r;
while (cin >> l >> r)
cout << calc(r) - calc(l - 1) << endl;
return 0;
}