洛谷 P2657 [SCOI2009]windy数

题意简述

求l~r之间不含前导零且相邻两个数字之差至少为2的正整数的个数

题解

数位DP

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
int a, b, l, x;
int num[20];
int dp[20][10];
int dfs(int len, int pre, bool limit, bool lead, int s = 0)
{
    if (len == 0) return !lead;
    if (!lead && !limit && ~dp[len][pre]) return dp[len][pre];
    int mx = limit ? num[len] : 9;
    for (register int i = 0; i <= mx; ++i)
        if (lead || abs(pre - i) >= 2)
            s += dfs(len - 1, i, limit && (i == mx), lead && !i);
    if (!lead && !limit) dp[len][pre] = s;
    return s;
}
int solve(int x)
{
    l = 0;
    memset(dp, -1, sizeof(dp));
    while (x) {num[++l] = x % 10; x /= 10; }
    return dfs(l, 0, 1, 1);
}
int main()
{
    scanf("%d%d", &a, &b);
    printf("%d\n", solve(b) - solve(a - 1));
}

洛谷 P2657 [SCOI2009]windy数

原文：https://www.cnblogs.com/xuyixuan/p/9905385.html