Description

　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，

在A和B之间，包括A和B，总共有多少个windy数？

Input

　　包含两个整数，A B。

Output

　　一个整数

Sample Input

【输入样例一】

1 10

【输入样例二】

25 50

Sample Output

【输出样例一】

9

【输出样例二】

20

HINT

【数据规模和约定】

100%的数据，满足 1 <= A <= B <= 2000000000 。

---

题解Here!

 

本蒟蒻的第一道数位$DP$板子题。。。

设$dp[i][j]$表示填到$i$位，这一位填$j$的合法方案数。

转移方程（想了我2天。。。）：

$$dp[i][j]=\sum_{|k-j|>=2}dp[i-1][k]$$

然后前面有$0$的情况预处理一下就好。

附代码：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int bit[11];long long A,B,dp[11][10];inline long long read(){	long long date=0,w=1;char c=0;	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}void make(){	int n=10;	for(int i=0;i<=9;i++)dp[1][i]=1;	for(int i=2;i<=n;i++)	for(int j=0;j<=9;j++){		for(int k=0;k<=j-2;k++)dp[i][j]+=dp[i-1][k];		for(int k=j+2;k<=9;k++)dp[i][j]+=dp[i-1][k];	}}long long solve(long long n){	int len=0;	long long ans=0;	while(n){		bit[++len]=n%10;		n/=10;	}	for(int i=1;i
          
           =1;i--){		for(int j=0;j
           
            =2)ans+=dp[i][j]; if(abs(bit[i+1]-bit[i])<2)break; } return ans;}int main(){ make(); A=read();B=read(); printf("%lld\n",solve(B+1)-solve(A)); return 0;}