【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));
}