数位DP 数字游戏
作者:
wyatt
,
2022-04-24 15:48:29
,
所有人可见
,
阅读 175
`#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <set>
using namespace std;
typedef long long LL;
const int N = 35;
int f[N][10]; // 一共 i 位 且 最高位为 j 的不降数的个数
void init()
{
for(int i = 0 ; i <= 9 ; i ++)f[1][i] = 1;
for(int i = 2 ; i <= 31 ; i ++)
{
for(int j = 0 ; j <= 9 ; j ++)
{
for (int k = j; k <= 9; ++k) {
f[i][j] += f[i - 1][k];
}
}
}
}
int dp(int n)
{
if(!n)return 1;
vector<int> nums;
while (n)nums.push_back(n % 10), n /= 10;
int ans = 0;
int last = 0;
for (int i = nums.size() - 1; i >= 0; --i) {
int x = nums[i];
for(int j = last ; j < x ; j++)
{
ans += f[i + 1][j];
}
if (last > x)break;
last = x;
if (!i)ans++;
}
return ans;
}
int main()
{
init();
int l , r ;
while (scanf("%d%d", &l, &r) != EOF) {
// cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;
}
return 0;
}