1587： 【例 3】Windy 数

1587： 【例 3】Windy 数

时间限制: 1000 ms 内存限制: 524288 KB
提交数: 596 通过数: 366
【题目描述】

原题来自：SCOI 2009

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

Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？
【输入】

一行两个数，分别为A,B。
【输出】

输出一个整数，表示答案。
【输入样例】

1 10

【输出样例】

9

【提示】

样例输入 2

25 50

样例输出 2

20

数据范围与提示：

20% 的数据，满足 1≤A≤B≤106 ；

100% 的数据，满足 1≤A≤B≤2×109 。

思路：
发现自己什么都不会qwq
这只是一个很基础的板子qwq
啊啊啊ε＝ε＝ε＝(#>д<)?

f[i][j]表示处理到第i位，第i位上的数字是j，首先在我们dfs之前要进行预处理，在预处理的时候就判断是否符合windy数定义
接下来对于所有小于x的数进行处理，因为我们的f[i][j]定义的是所有不超过上界的数，所以对于每一位都不超过x所对应的每一位的上界的数直接加上f[i][j]就可以
但是对于这样的数：有某一位达到了上界，我们就不能通过f[i][j]数组来转移，这时候应当对这样的数特殊处理，处理方式是枚举上界，枚举当前所在位上的数，如果符合windy数定义，那么就加上f[i][j]（因为这个时候的确符合f[i][j]未达到上界），ans+=f[i][j]

代码：

#include
#define ll long long 
#define maxn 15
using namespace std;

ll a,b;
ll f[maxn][maxn];
ll p[maxn];

void prepare()
{
//	f[0][0]=0;
	p[0]=1;
	for(int i=1;i<=13;i++) p[i]=p[i-1]*10;
	for(int i=0;i<=9;i++) f[1][i]=1;
	for(int i=2;i<=13;i++)
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
			{
				if(abs(k-j)>=2) f[i][j]+=f[i-1][k]/*,cout<=1;i--)
	{
		y=x/p[i-1];
		for(int j=0;j=2) ans+=f[i][j]/*,cout<>a>>b;
	prepare();
//	prepare();
//cout<

原文：https://www.cnblogs.com/yxr001002/p/14437982.html