AcWing 1082. 数字游戏
原题链接
中等
作者:
wangyj
,
2021-01-21 08:59:47
,
所有人可见
,
阅读 330
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int f[15][15];
int dp(int n)
{
if(!n)return 1;
vector<int>nums;
while(n)nums.push_back(n%10),n/=10;
int ans=0,end=0,i,x,j;
for(i=nums.size()-1;i>=0;i--){
x=nums[i];
for(j=end;j<x;j++)ans+=f[i+1][j];
if(x<end)break;
end=x;
if(!i)ans++;
}
return ans;
}
int main()
{
int i,j,k,l,r;
for(i=0;i<=9;i++)f[1][i]=1;
for(i=2;i<15;i++)for(j=0;j<=9;j++)for(k=j;k<=9;k++)f[i][j]+=f[i-1][k];
while(cin>>l>>r)printf("%d\n",dp(r)-dp(l-1));
return 0;
}