AcWing 1083. Windy数
原题链接
中等
作者:
ZTEG
,
2019-11-18 21:46:44
,
所有人可见
,
阅读 1480
一个模板走天下(滑稽)
#include<bits/stdc++.h>
using namespace std;
int x,y;
int tot,hhh;
int a[100];
int f[100][22];
int dfs(int x,int s,bool eg)
{
int g=eg?a[x]:9;
if(!x)
return 1;
if(!eg&&f[x][s])
return f[x][s];
int ans=0;
for(int i= x==hhh?1:0;i<=g;i++)
if(abs(i-s)>=2)
ans+=dfs(x-1,i,eg&&i==a[x]);
if(!eg)
f[x][s]=ans;
return ans;
}
int sss(int x)
{
tot=0;
memset(a,0,sizeof(a));
while(x)
{
a[++tot]=x%10;
x/=10;
}
int ans=0;
for(hhh=1;hhh<=tot;hhh++)
ans+=dfs(hhh,20,hhh==tot);
return ans;
}
int main()
{
cin>>x>>y;
cout<<sss(y)-sss(x-1)<<endl;
return 0;
}