AcWing 1082. 数字游戏
原题链接
中等
作者:
Anoxia_3
,
2021-05-01 00:44:03
,
所有人可见
,
阅读 463
#include <iostream>
#include <vector>
using namespace std;
const int N = 15;
int l , r;
int f[N][N];//f[i][j]表示:一共有i位,且最高位是j的数的个数
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 < 10 ; j++)
for(int k = j ; k < 10 ; k++)//枚举一共有i-1位,且最高位为k的情况
f[i][j] += f[i - 1][k];
}
int dp(int n)
{
if(!n) return 1;//0是一个不降数
vector<int> nums;
while(n) nums.push_back(n % 10) , n /= 10;
int res = 0;
int last = 0;//记录上一个数,因为开始时前面没有数字,因此不受限制,可以从0开始
for(int i = nums.size() - 1 ; i >= 0 ; i--)
{
int x = nums[i];
//左分支
for(int j = last ; j < x ; j++)//为了保证不降序,枚举取到数从last开始,且为了最终的数字不超过,所以要<x
res += f[i + 1][j];//答案加上一共i+1位,且最高位为j的数的个数
if(x < last) break;//如果降序,直接退出
last = x;//更新last
if(!i) res++;
}
return res;
}
int main()
{
init();
while(cin >> l >> r)
{
cout << dp(r) - dp(l - 1) << endl;
}
}
请问
for(int j = last ; j < x ; j++)
为啥不能等于x
,没太明白。这里计算的是左分支,就是当前这位是小于x的情况,等于x的情况放在右分支中继续计算,可以看一下y总画的那棵树
哦哦我明白了 谢谢啦啊