P2657 [SCOI2009] windy 数

较裸的数位DP题。定义 $f _ {i, j}$ 表示 $i$ 为数中最高位为 $j$ 的满足条件的数的个数。则有
$$
f _ {i, j} = \sum _ {k = 0} ^ 9 f _ {i - 1, k} [abs(j - k) \ge 2]
$$
分别计算 $[1, a)$ 和 $[1, b + 1)$ 中的答案，对于 $[1\ldots x)$ 的答案，分为三种情况：

长度小于 $x$ ，答案直接加；
长度等于 $x$ ，加上最高位的数小于 $x$ 的答案；
长度等于 $x$ ，最高位的数等于 $x$ ，枚举前若干位和 $x$ 相等，统计答案。

查看代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 12;
int n[N], f[N][N];
void init()
{
    for (int i = 0; i < 10; i++)
        f[1][i] = 1;
    for (int i = 2; i <= 10; i++)
        for (int j = 0; j < 10; j++)
            for (int k = 0; k < 10; k++)
                if (abs(j - k) >= 2)
                    f[i][j] += f[i - 1][k];
}
int solve(int x)
{
    memset(n, 0, sizeof n);
    int len = 0;
    while (x)
    {
        n[++len] = x % 10;
        x /= 10;
    }
    int res = 0;
    for (int i = 1; i < len; i++)
        for (int j = 1; j < 10; j++)
            res += f[i][j];
    for (int i = 1; i < n[len]; i++)
        res += f[len][i];
    for (int i = len - 1; i; i--)
    {
        for (int j = 0; j < n[i]; j++)
            if (abs(j - n[i + 1]) >= 2)
                res += f[i][j];
        if (abs(n[i + 1] - n[i]) < 2)
            break;
    }
    return res;
}
int main()
{
    init();
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d", solve(b + 1) - solve(a));
    return 0;
}