算法

(数位DP)

数位 DP 鼻祖题。显然可以把答案写成两个前缀相减的形式。
先 DP 出所有的方案，设 f(i,j) 代表最高位为 j 的 i 位数中一共有多少个 windy 数，考虑依次枚举最高位，有

$$f(i, j)=\sum_{k=0}^{j-2} f(i-1, k)+\sum_{k=j+2}^{9} f(i-1, k)$$

接下来从高到低计算方案，先确定一个最高位，然后找到若干个合法的下一位，在 DP 状态里面直接拿出这个答案。最后对于部分是合法的部分，递归处理即可。

C++ 代码

#include <iostream>

#define inf 0x7fffffff
using namespace std;
using ll = long long;

int f[15][15], base[15];
int A, B;
// f(i, j) 一个i位数j开头，一共有多少个windy数
// base[i] = 10 ^ (i - 1)

void init() {
    base[1] = 1;
    for (int i = 2; i <= 10; ++i) 
        base[i] = base[i - 1] * 10;
    for (int i = 0; i <= 9; ++i) f[1][i] = 1;
    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]; 
} 

int cnt(int n) {
    if (!n) return 0;
    int tmp = 0, w = 10;
    while (base[w] > n) w--; // w是位数 
    for (int i = 1; i < w; ++i) 
        for (int j = 1; j <= 9; ++j)
            tmp += f[i][j];
    int cur = n / base[w]; // 当前最高位的数字
    for (int i = 1; i < cur; ++i) tmp += f[w][i];
    n %= base[w]; // 舍弃最高位
    int pre = cur;
    for (int i = w - 1; i; --i) {
        cur = n / base[i];
        if (i != 1) {
            for (int j = 0; j < cur; ++j)
                if (abs(pre - j) >= 2) tmp += f[i][j];
        }
        else {
            for (int j = 0; j <= cur; ++j)
                if (abs(pre - j) >= 2) tmp += f[i][j];
        }
        if (abs(cur - pre) < 2) break;
        pre = cur;
        n %= base[i];
    } 
    return tmp;
} 

int main() {
    init();
    cin >> A >> B;

    cout << cnt(B) - cnt(A - 1) << '\n';

    return 0;
}