AcWing 1082. 数字游戏 记忆化搜索 初学者写法
原题链接
中等
作者:
cc_25
,
2024-11-06 09:58:14
,
所有人可见
,
阅读 4
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=15;
int l,r,cnt;
int nb[N];
int dp[N][N][2];
int dfs(int pos,int last,int flag)
{
if(pos==0) return 1;
if(dp[pos][last][flag]!=-1) return dp[pos][last][flag];
int ans=0;int mx=flag? nb[pos]:9;
for(int i=last;i<=mx;i++)
{
ans+=dfs(pos-1,i,flag&&nb[pos]==i);
}
return dp[pos][last][flag]=ans;
}
int get(int x)
{
cnt=0;
memset(dp,-1,sizeof dp);
while(x>0) nb[++cnt]=x%10,x=x/10;
return dfs(cnt,0,1);
}
signed main()
{
while(cin>>l>>r){
cout<<get(r)-get(l-1)<<endl;}
return 0;
}