AcWing 1083. Windy数
原题链接
中等
作者:
最后五分钟
,
2025-04-03 11:06:51
· 江西
,
所有人可见
,
阅读 3
using namespace std;
const int N=45;
int f[N][10];
int dp(int t)
{
if(!t)return 0;//如果前导0与最大值重合,会出现ls判断的重复计数
vector<int> num;
num.push_back(t%10),t/=10;
while(t)num.push_back(t%10),t/=10;
int ls=-10;
int res=0;
for(int i=num.size()-1;~i;i--)
{
int x=num[i];
for(int j=i==num.size()-1;j<=x-1;j++)
{
if(abs(ls-j)>=2)res+=f[i+1][j];
}
if(abs(x-ls)<2)break;
ls=x;
if(!i)res++;
}
//前导0不能统计在上面的for循环内,如果出现break,后面部分的前导的0就统计不到
for(int i=num.size()-1;~i;i--)
{
for(int j=1;j<=9;j++)res+=f[i][j];
}
return res;
}
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<=9;j++)
for(int k=0;k<=9;k++)
if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int l,r;
cin>>l>>r;
init();
cout<<dp(r)-dp(l-1)<<endl;
return 0;
}