主题： https://www.AC wing.com/problem/content/1085 /
题意： Windy定义Windy数。 不包含开头的零、相邻的两个数字之差至少为2的正整数称为Windy数。 Windy想知道a和b之间，包括a和b在内，一共有多少个Windy数。 1ab210 ^ 9
示例： [ 110 ]9 [ 2550 ]20
问题：数字dp。
首先，旧的数字dp类型要求满足[l，r]中主题限制的数量。 只要求出[0，r]的个数和[0，l-1]的个数，如果两个相互减少的话，就是[l，r]的个数。
接下来，首先进行dp的预处理。 f[i][j]表示全部为I位、最高位为j时可执行的计划数。 有了该预处理，从最高位开始按各位列举可以选择的数，如果有人是x，则列举与[0，x-1]到x的差为2以上的数，将该位的最高位列举的数的方案数全部重叠即可。
但是，有需要特别注意的地方。 顶级枚举[1，x-1]就可以了。 不要从0开始列举。 否则会出现问题。 从0开始列举时，f[i][0]会重叠在最上面。 这里会发生问题。
例如，两个人的时候，枚举的最高位是0，答案是09-08-07-06-05-04-03-02。 答案是8，但答案是9。 因为1也是答案。 例如，样本[ 1，10 ]的答案是9，所以答案是错误的。 这里两个人时对答案的影响是1。 然而，如果最高为=1，则其它位可列举0而不产生任何影响。
最高位为0的解决方案其实很容易解决。 例如，如果n是第8位的话，在下面直接暴力地跑位数为1、2、3、4、5、6、7的情况就可以了。 因为排在第8位的时候已经在位数dp中跑完了。 最高位为0时，为其余所有情况。 在这些情况下一定会小于n
# include bits/stdc.h/# defineintlonglong # definepbpush _ back # definepiipairint，int # definemprmake _ pair # definepaire typedef unsigned long lll； const int inf=0x3f3f3f3f； constllinf=0x 3f 3f 3f 3f 3f 3f 3f 3f 3f 3f 3f 3f 3f 3f 3f； 用户命名空间STD； 常数int n=15； int f[N][N]； //f[i，j]共有I位，最高位为j的计划数void init ()//首先为1位时for(intI=0； i=9； I ) f(1) ) I )=1； //dp的跳出共有I位，最高位为j的方案数for(intI=2； i N； I ) for(intj=0； j=9； j ) for(intk=0； k=9； k ) if(ABS(j-k )=2) f[i][j] =f[i - 1][k]； //printf(%d%d(n )，f[1][0]，f[2][0] )； (intDP ) intn ) if (！ n )返回0； 向量int nums； while(n ) nums.emplace_back ) n /=10 ) n /=10； int res=0； int last=-2； //初始保证0-9不受last的影响//从最高位开始列举各位for (inti=nums.size )- 1； i=0； I--}{intx=nums[I]； //如果是最高位，则从1开始列举，0的情况特殊，向下单独弹出的结果for(intj=I==nums.size )- 1； j x； j({if ) ABS(j-last )=2) res =f[i 1][j]； (//如果该位置和前面的位置之差小于2，则不需要跑if(ABS(x-last )=2) last=x )； //如果还没有跳出，本身也是if(I ) res； () ) /暴力行驶位数n小的所有情况，由于这些情况小于n，只要满足限制条件，就可以执行的方案) /，与n位相同的数量，在高位的dp中已经for(intI=1； i nums.size (； I ) for(intj=1； j=9； j ) res =f[i][j]； 返回RES； }signed main () ) { init )； int l，r； cin l r； printf(%d(n )、DP(r )-DP (l-1 )； 返回0； }