https://loj.ac/problem/10165
题目描述
??定义不含前导\(0\)且相邻两个数字之差至少为\(2\)的正整数称为\(windy\)数，求区间\([A,B]\)内的\(windy\)数的个数。
思路
??这里我们还是先把数位\(dp\)的记搜莫不套上去，不过注意这里的前导\(0\)会对答案产生影响，一串前导\(0\)依旧满足条件，所以我们可以特别记录一下这种情况，其余的部分基本按照模板来即可。
代码
#include<bits/stdc++.h>
using namespace std;
int f[20][20],p[20];
int dfs(int x,int s,int flag)
{
if(x==0)return 1;
if(!flag&&~f[x][s])return f[x][s];
int res=0,end=flag?p[x]:9;
for(int i=0;i<=end;i++)
{
if(i==0&&s==11)res+=dfs(x-1,11,flag&&i==end);
else if(abs(i-s)>=2)res+=dfs(x-1,i,flag&&i==end);
}
if(!flag)f[x][s]=res;
return res;
}
int solve(int a)
{
memset(p,0,sizeof(p));
memset(f,-1,sizeof(f));
int cnt=0;
while(a)
{
p[++cnt]=a%10;
a/=10;
}
return dfs(cnt,11,1);
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("%d",solve(b)-solve(a-1));
}