【OI做题记录】【BZOJ】【SCOI2009】windy数

试题编号：BZOJ1026

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

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

输入描述

包含两个整数，A B。

输出描述

　一个整数

输入样例

【输入样例一】

1 10

【输入样例二】

25 50

输出样例

【输出样例一】

9

【输出样例二】

20

【数据规模和约定】

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

试题分析

很明显强行枚举时间复杂度为O（2*10^10）绝对是超时的（按每个数10位算）

我们就必须用优化了：我们发现，对于一个长度为len的windy数个数的话，他是包含了部分长度为len-1的windy数个数的。换一种说法，一个长度len的windy数，后面len-1位也是windy数。而且我们明明已经求出后len-1位是windy数，还要傻傻地将整个长度为len的windy数看一次。

这又是重复子问题，又是DP。而且是数位DP。

数位DP并不好想，也不好看出来。我们经常要将一个数拆开来就出子问题。

做法：

用一个f数组存储，f[i][j]表示长度为i，最高位是j的windy数个数。

我们可以推出方程

f[i][j]+=f[i-1][k];(abs(k-j)>=2)
           

先做一次预处理再说：

void restart()
{
	memset(f,0,sizeof(f));
	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++)//当前（i）位的数 
	for(int k=0;k<=9;k++)//i-1位的数 
	{
	if(abs(k-j)>=2)f[i][j]+=f[i-1][k];
	} 
}
           

然后呢，假如我有一个方法求出不大于k的所有windy数个数，则答案为：

done(y+1)-done(x);

接下来讲讲怎么求不大于k的windy数，可以分成两类：

1、位数小于k的所有windy数

2、位数等于k的所有windy数

其中第二类：

假设最高位不相同，则求出所有最高位小于k最高位的windy数；

假设最高位相同，次高位不相同，则求出所有最高位小于k次高位的、长度为len(k)-1的windy数；

以此类推。

代码

不给你看

#include<cstdio>
#include<cstring>
int st,ed;
int f[15][10];
int abs(int x)
{
	return x<0?(-x):x;
}
void restart()
{
	memset(f,0,sizeof(f));
	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++)//当前（i）位的数 
	for(int k=0;k<=9;k++)//i-1位的数 
	{
	if(abs(k-j)>=2)f[i][j]+=f[i-1][k];
	} 
}
int done(int x)
{
	int soy=x;
	int s[15],len=0;
	while(soy!=0){
		len++;
		s[len]=soy%10;
		soy/=10;
	}
	int ans=0;
	for(int i=1;i<len;i++)
	for(int j=1;j<=9;j++)
	ans+=f[i][j];
	
	for(int i=1;i<s[len];i++)ans+=f[len][i];
	
	for(int i=len-1;i>=1;i--)//此时保证len~i+1位相等 
	{
		for(int j=0;j<s[i];j++) 
		if(abs(j-s[i+1])>=2)ans+=f[i][j];
		if(abs(s[i]-s[i+1])<2)break;
	}
	return ans;
}
int main()
{
	
	
	restart();
	/*for(int i=1;i<=10;i++)
	{
	for(int j=0;j<=9;j++)
	printf("%d ",f[i][j]);
	printf("\n");
	}*/
	scanf("%d %d",&st,&ed);
	printf("%d\n",done(ed+1)-done(st));
}