洛谷P2657 [SCOI2009]windy数 题解（数位dp）

description：

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

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

$1\le A\le B\le 2000000000$1≤A≤B≤2000000000

solution:

数位dp。

设 $f\left[i\right]\left[j\right]$f[i][j]表示共i位，最高位为j时的方案总数

• 当 $abs(j-k)>=2$abs(j−k)>=2时
• $f\left[i\right]\left[j\right]+=f[i-1]\left[k\right]$f[i][j]+=f[i−1][k]

整体上运用前缀和思想，将题目转换为求 $[0,R]$[0,R]的结果，然后相减

code:

#include<cstdio>
#include<cstring>
using namespace std;
int abs(int x)//手写绝对值
{
	if(x<0)return -x;
	return x;
}
int f[15][15];
void init()
{
	for(int i=0;i<=9;i++)//一位数时总是可以的
	{
		f[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)//先预处理出所有的情况
				{
					f[i][j]+=f[i-1][k];//如solution
				}
			}
		}
	}
}
int a[25];
int work(int x)
{
	memset(a,0,sizeof(a));//清空a数组，但是好像也不需要
	int cnt=0,ans=0;
	while(x)//将x每一位取出来，方便后面使用
	{
		a[++cnt]=x%10;
		x=x/10;
	}
	for(int i=1;i<cnt;i++)//如果位数就小于x，那就为所欲为了（后面放什么数都行）
	{
		for(int j=1;j<=9;j++)
		{
			ans+=f[i][j];
		}
	}
	for(int i=1;i<a[cnt];i++)//如果最高位有但是小于x，那也可以为所欲为了（后面放什么数都行）
	{
		ans+=f[cnt][i];
	}
	for(int i=cnt-1;i>=1;i--)//如果最高位是x
	{
		for(int j=0;j<a[i];j++)//只可以放到小于对应位的
		{
			if(abs(j-a[i+1])>=2)//如果两个数位之间的差满足条件
			{
				ans+=f[i][j];
			}
		}
		if(abs(a[i+1]-a[i])<2)break;//最后再判一下，因为如果连这两位之间都小于2了，那么后面的更没戏了（？）
	}
	return ans;
}
int main()
{
	init();
	int A,B;
	scanf("%d%d",&A,&B);
	printf("%d\n",work(B+1)-work(A));
	return 0; 
}