P2657 [SCOI2009] windy 数

P2657 [SCOI2009] windy 数

Meaning

求区间 $[a,b]$ 内不含前导零且相邻两位相差大于 $1$ 的数的个数。

Sol

数位 dp 板子题。

考虑设计 $dp_{i,j,0/1,0/1}$ 表示选取到第 $i$ 位，上一位放置 $j$，是否仍为前导零，是否恰好与为临界值。

考虑差分简化边界，使用记忆化搜索的方式确定 dp 方向，每次搜索判断边界和条件：

• 是否仍为临界值；
• 是否仍为前导零；
• 是否相差大于 $1$。

Detail

1. 由于差分需要 dp 两次，注意清空数组和变量。

Code

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 1e2 + 1e1;
const lint INF = 1e18 + 1e9;

int dp[MAXN][MAXN], a[MAXN];
int x, y, cnt;

int Dfs(int dep, int pre, bool top, bool lim) {
    if (!dep) return (top ? 0 : 1);
    if (!lim && !top && dp[dep][pre] != -1) return dp[dep][pre];
    int res = 0;
    for (int i = 0; i <= (lim ? a[dep] : 9); i ++) {
        if (top) res += Dfs(dep - 1, i, i == 0, lim & (i == a[dep]));
        else if (abs(i - pre) > 1) res += Dfs(dep - 1, i, false, lim & (i == a[dep]));
    }
    if (!lim && !top) dp[dep][pre] = res;
    return res;
}

int Calc(int num) {
    memset(a, 0, sizeof(a)), memset(dp, 255, sizeof(dp)), cnt = 0;
    while (num) a[++ cnt] = num % 10, num /= 10;
    return (!cnt ? 0 : Dfs(cnt, inf, true, true));
}

int main(void) {

    x = readint, y = readint;
    printf("%d\n", Calc(y) - Calc(x - 1));

    return 0;
}