description:

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

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

1 A B 2000000000 1\leq A\leq B\leq2000000000 1AB2000000000

solution:

数位dp。

f [ i ] [ j ] f[i][j] f[i][j]表示共i位,最高位为j时的方案总数

  • a b s ( j k ) > = 2 abs(j-k)>=2 abs(jk)>=2
  • f [ i ] [ j ] + = f [ i 1 ] [ k ] f[i][j]+=f[i-1][k] f[i][j]+=f[i1][k]

整体上运用前缀和思想,将题目转换为求 [ 0 , R ] [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; 
}