BZOJ1026 - Click Here
Description
windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？
Input
包含两个整数，A B。
100%的数据，满足1<=A<=B<=2000000000。
Output
一个整数。
Solutions
数位DP的入门题？
询问[a,b]区间内的windy数。很显然，只要求出[1,a-1]的windy数和[1,b]的windy数就可以得到答案。
因此，现在问题就是如何求[1,k]区间内的windy数。
定义$f[i][j]$为位数为$i$，最高位为$j$且最高位与数字$k$第$i$位不相等的windy数；
定义$g[i][j]$为位数为$i$，最高位为$j$且最高位与数字$k$第$i$位相等的windy数。
根据windy数的定义，很容易得到递推式：
$f[i][j]=\sum f[i-1][k],|j-k|>1$
$g[i][j]=g[i-1][num_{i-1}]+\sum_{p=0}^{num_{i-1}-2}f[i-1][p]$，其中$num_{i}$表示数字$k$的第i位。
答案即为$\sum_{i=1}^{len-1} \sum_{j=1}^{9}f[i][j]+\sum_{j=1}^{num_{len}-1}f[len][j]+g[len][num_{len}]$，其中$len$为k的位数。
CODE
CODE - Click Here