前言

得多练练DP...需熟练掌握DP的多种类型...

题目

windy定义了一种windy数。
不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。
windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

Input

两个整数，A B。

Output

一个整数，表示A~B中有多少个windy数。

Sample Input

1 10

Sample Output

9

【数据范围】

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

分析

数的范围很大，暴力肯定不行

正解：【数位DP】，推荐经典例题【不要62】

（这些好像吴老师之前都讲过，只是隔了很久，都忘了...汗）

思路来自博客（特别鸣谢）：https://blog.csdn.net/zz_ylolita/article/details/50754618

讲的很详细，这里就不赘述了

---

纠结了一会，还是决定自己细说一下“一、二、三部分”（因为当时自己理解地很艰难）：

设X=7634，

第一部分：ans+=1_ _ _+2_ _ _+...+6_ _ _ 的种类数

第二部分：ans+=_ _ _+_ _+_ 的种类数

第三部分：ans+=7_ _ _的种类数，要特殊处理

具体见代码，会更好理解

考试暴力代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a,b,ans;
bool Check(ll x)
{
	bool flag=true;
	int a,tmp=-2;
	while(x>0)
	{
		a=x%10;
		x/=10;
		if(abs(a-tmp)<2)
		{
			flag=false;
			break;
		}
		tmp=a;
	}
	return flag;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	for(int i=a;i<=b;i++)
		if(Check(i))
			ans++;
	printf("%lld",ans);
	return 0;
}
//暴力超时... 

AC代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll dp[15][15];
ll a,b;
int len,digit[15];
void Prepare()
{
	for(int i=0;i<=9;i++)
		dp[1][i]=1;
	for(int i=2;i<=10;i++)
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
				if(abs(j-k)>=2)
					dp[i][j]+=dp[i-1][k];
}
ll Solve(ll x)
{
	ll ret=0;
	int len=0;
	if(x==0)
		return 0;
	while(x>0)
	{
		digit[++len]=x%10;
		x/=10;
	}
	for(int i=1;i<=digit[len]-1;i++)
		ret+=dp[len][i];
	for(int i=len-1;i>0;i--)
		for(int j=1;j<=9;j++)
			ret+=dp[i][j];
	for(int i=len-1;i>=1;i--)
	{
		for(int j=0;j<=digit[i]-1;j++)
			if(abs(digit[i+1]-j)>=2)
				ret+=dp[i][j];
		if(abs(digit[i+1]-digit[i])<2)
			break;
	}
	return ret;
}
int main()
{
	scanf("%lld%lld",&a,&b);
	Prepare();
	printf("%lld",Solve(b+1)-Solve(a));
	return 0;
}