windy界说了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包孕A和B，总共有几多个windy数？
输入
包罗两个整数，，A B。
输出
一个整数，暗示答案
样例输入
【输入样例一】
1 10
【输入样例二】
25 50
样例输出
【输出样例一】
9
【输出样例二】
20
题解
数位dp
快联赛了重写了一下，发明以前写的太傻逼了= =
由于加一个数位的孝敬只与最高位有关，因此设 $f[i][j]$ 暗示 $i$ 位数，最高位为 $j$ 的数的个数。
那么显然可以得到 $f[i][j]=\sum\limits_{|j-k|\le 2}f[i-1][k]$ 。
预措置惩罚惩罚出 $f$ 数组后即可进行数位dp。
先把位数不满的算上，然后再从高位到低位把该位不满的插手答案中。
此时需要记录上一个数位是什么，在枚举当前数位时需要满足当前位的条件。并且如果上一个与当前数位孕育产生斗嘴则不再有满足条件的数，该当跳出循环。
把询问区间转化为 $[1,n)$ 的半开半闭区间更容易措置惩罚惩罚一些。
代码中为了制止一些细节（好比最高位只能措置惩罚惩罚到 $2*10^9$ 之类的），开了long long。
#include <cstdio> typedef long long ll; ll f[11][10] , b[11]; inline int abs(int x) { return x > 0 ? x : -x; } void init() { int i , j , k; b[0] = 1 , b[1] = 10; for(i = 0 ; i < 10 ; i ++ ) f[1][i] = 1; for(i = 2 ; i < 11 ; i ++ ) { b[i] = b[i - 1] * 10; for(j = 0 ; j < 10 ; j ++ ) for(k = 0 ; k < 10 ; k ++ ) if(abs(j - k) >= 2) f[i][j] += f[i - 1][k]; } } ll calc(ll n) { int i , j , last = -1 , di = 1; ll ans = 0; for(i = 1 ; b[i] <= n ; i ++ ) for(j = 1 ; j < 10 ; j ++ ) ans += f[i][j]; for( ; i ; i -- ) { for(j = di ; j < n / b[i - 1] % 10 ; j ++ ) if(abs(j - last) >= 2) ans += f[i][j]; if(abs(n / b[i - 1] % 10 - last) < 2) break; last = n / b[i - 1] % 10 , di = 0; } return ans; } int main() { init(); ll n , m; scanf("%lld%lld" , &n , &m); printf("%lld\n" , calc(m + 1) - calc(n)); return 0; }
【bzoj1026】[SCOI2009]windy数 数位dp