题目描述

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 Windy 数。

Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？

数据范围

$1≤A≤B≤2×10^9$

样例

输入
1 10

输入
9

数位Dp

假设我们当前枚举到第i位(设共有n位)，且第i位上的数字为x，那么对于答案中第i位数字j来说，有两类：

• 1.0~x-1 (如果第i位是最高位，这里是1~x-1)
  括号中提到的1~x-1后面会解释 ,我们用last记录上一位的数字，然后枚举j，如果abs(j-last) >= 2 就累加答案，res += f[i+1][j];

• 2.x
  不需要枚举j，last = x,再枚举之后的数位即可

上述做完之后，由于上面的答案都是n位的，对于数位个数低于n的，再累加到答案中就行了

f数组的处理

f[i][j] 表示一共有i位，且最高位数字为j的满足windy数定义的数的个数

状态转移： 因为第i位是j已经确定，考虑第i-1位，设第i-1位数字为k，那么根据windy数定义只要abs(k-j) >= 2就可以转移过来

$ f[i][j] = \sum_{k=0}^{9}if(abs(k-j)>=2) f[i-1][k] $

关于前导0

上面提到了枚举的第i位是最高位，那么不能填0，这里解释一下，如果我们填0，那么答案就会加上f[i+1][0],，举这样一个例子，
对于数字13，他是满足windy数定义的，那么加上前导0之后的013就不会被f[3][0]加进去，原因就是abs(0-1)<2，这样就导致答案漏掉。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][N];  //f[i][j] 表示一共有i位，且最高为是数字j的满足wingy数定义的数的个数

void init(){
    for(int i = 0; i<=9; i++) f[1][i] = 1;
    for(int i = 2; i<=9; i++)
        for(int j = 0; j<=9; j++)
            for(int k = 0; k<=9; k++)
                if(abs(k-j)>=2) f[i][j] += f[i-1][k];
}

int dp(int n){
    int res = 0,last = -10;

    vector<int> a;
    while(n)a.push_back(n%10),n/=10;

    int len = a.size()-1;
    //答案是a.size()位的
    for(int i =len; i>=0; --i){
        int x = a[i];
        for(int j = (i==len); j<x; ++j)   //最高位从1开始
            if(abs(j-last)>=2) res += f[i+1][j];

        if(abs(x-last)<2) break;  //不满足定义，直接break
        last = x;

        if(!i) res ++;
    }
    //答案小于a.size()位的
    for(int i = 1; i<=len; i++)
        for(int j = 1; j<=9; j++)
            res += f[i][j];

    return res;
}
int main()
{
    init();
    int l,r;
    cin>>l>>r;
    cout<<dp(r)-dp(l-1);
    return 0;
}