AcWing 1082. 数字游戏
原题链接
中等
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
int a , b;
vector<int> v;
int dp[15][11][2];
int dfs(int pos ,int pre , bool lm)
{
if(dp[pos][pre][lm] != -1) return dp[pos][pre][lm];
if(pos == v.size()) return 1;
int ans = 0 , up = lm ? v[pos]:9;
if(pre == 10)
{
ans += dfs(pos + 1 , 10 , false);
for(int i = 1 ; i <= up ; i ++) ans += dfs(pos + 1 , i , lm ? (i == up):(false));
}else
{
for(int i = 0 ; i <= up ; i ++)
{
if(i >= pre) ans += dfs(pos + 1 , i , lm ? (i == up):(false));
}
}
dp[pos][pre][lm] = ans;
return ans;
}
int cnt(int num)
{
if(num == 0) return 1;
memset(dp , -1,sizeof(dp));
v.clear();
while(num)
{
v.push_back(num % 10);
num /= 10;
}
reverse(v.begin() , v.end());
return dfs(0 , 10 , true);
}
void solve()
{
while(cin >> a >> b)
{
cout << cnt(b) - cnt(a - 1) <<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}