Windy数

昨天看了数位dp，虽然还是有点没懂不过水一发板子题先
题目链接：[SCOI2009]windy数

---

这道题大概是数位dp的模板了，状态转移方程也比较显然。
设f[i][j]表示i位数，首位是j的windy数的数量，则容易有状态转移方程：

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

然后我们用这样几个循环先把这个f数组预处理一下（即在数据范围内的所有的windy数的数量）

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];

计算区间[A,B]内的windy数，可以考虑前缀和，求出[0,B]内的windy数和[0,A-1]内的windy数，然后相减输出。

对于求[0,B]区间内的windy数，设B有k位，考虑分为三段：

1. 求出k-1位长的windy数
2. 求出“k位长，首位小于B的最高位”的windy数
3. 求出k位长，首位为B的最高位的windy数

这样就可以囊括完所有的部分

对于第三步，我们可以通过一个这样的过程来求解：
首先统计长度为k-1,最高位为i(0<=i<=B[k-1]-1)的windy数的数量，然后统计最高位是B[k-1]的windy数，特判一下若abs(B[i]-B[i-1])<2，则说明不符合条件，没有最高位为B[i],次高位是B[i-1]的windy数，就跳出循环。最后若i==1则说明还有windy数，统计的ans++。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long x,y;
long long f[15][15];
long long digit[15];
void dp(){
	memset(f,0,sizeof(f));
	for(int i=0;i<=9;i++)		//一位数都是windy数 
		f[1][i]=1;
	for(int i=2;i<=10;i++)				//状态转移方程：f[i][j]=sum(f[i-1][k])(abs(j-k)>=2) 
		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];
}

long long solve(long long x){
	memset(digit,0,sizeof(digit));
	long long cnt=0,ans=0;
	if(x==0)return 0;
	while(x){			 
		digit[++cnt]=x%10;
		x/=10;
	}
	for(int i=1;i<=cnt-1;i++)
		for(int j=1;j<=9;j++)
			ans+=f[i][j];
	
	for(int i=1;i<digit[cnt];i++)
		ans+=f[cnt][i];
	
	for(int i=cnt-1;i>=1;i--){
		for(int j=0;j<=digit[i]-1;j++)
		if(abs(j-digit[i+1])>=2)ans+=f[i][j];
		if(abs(digit[i]-digit[i+1])<2)break;
		if(i==1)ans++;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&x,&y);
	dp();
	printf("%lld",solve(y)-solve(x-1));
	return 0;
}