AcWing 1083. Windy数
原题链接
中等
#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 , int 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(abs(i - pre) >= 2) ans += dfs(pos + 1 , i , lm ? (i == up):(false));
}
}
dp[pos][pre][lm] = ans;
return ans;
}
int cnt(int num)
{
v.clear();
memset(dp , -1 , sizeof(dp));
while(num)
{
v.push_back(num % 10);
num /= 10;
}
reverse(v.begin() , v.end());
return dfs(0 , 10 , true);
}
void solve()
{
cin >> a >> b;
cout << cnt(b) - cnt(a - 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}