题目传送门
题目描述
$windy$定义了一种$windy$数。不含前导零且相邻两个数字之差至少为$2$的正整数被称为$windy$数。
$windy$想知道，在$A$和$B$之间，包括$A$和$B$，总共有多少个$windy$数？
输入格式
包含两个整数，$A,B$。
输出格式
输出一个整数，表示答案。
样例
样例输入1：
1 10
样例输出1：
9
样例输入2：
25 50
样例输出2：
20
数据范围与提示
对于$20%$的数据，满足$1\leqslant A\leqslant B\leqslant {10}^6$；
对于$100%$的数据，满足$1\leqslant A\leqslant B\leqslant 2\times {10}^9$。
题解
一道数位$DP$的板子题。
定义$dp[i][j]$表示考虑到第$i$位，上一个数是$j$的方案数。
搜索统计答案即可。
但是还需要注意两个点：
$alpha.$不能有前导$0$，搜索的时候打一个标记记一下就好了。
$beta.$搜索的时候不能超过那个数最高位的限制。
然而，这并不是我想说的重点！！！
注意这两个代码的不同之处：
然而，在洛谷上：
旋转懵逼～～～
自家$OJ$上：
不过，结局还是好的吧……
代码时刻
#include<bits/stdc++.h>
using namespace std;
int A,B;
int num[10];
int dp[10][10];
int dfs(int lent,int last,bool maxn,bool zero)
{
if(!lent)return 1;
if(!maxn&&!zero&&dp[lent][last]!=-1)return dp[lent][last];
int cnt=0,maxx=maxn?num[lent]:9;
if(abs(last)>=2)
if(zero)cnt+=dfs(lent-1,-20020923,maxn&&!maxx,1);
else cnt+=dfs(lent-1,0,maxn&&!maxx,0);
for(int i=1;i<=maxx;i++)
if(abs(last-i)>=2)
cnt+=dfs(lent-1,i,maxn&&(maxx==i),0);
if(!maxn&&!zero)dp[lent][last]=cnt;
return cnt;
}
int wzc(int x)
{
memset(dp,-1,sizeof(dp));
num[0]=0;
while(x)
{
num[++num[0]]=x%10;
x/=10;
}
return dfs(num[0],-20020923,1,1);
}
int main()
{
scanf("%d%d",&A,&B);
printf("%d",wzc(B)-wzc(A-1));
return 0;
}
rp++