题目地址：洛谷：【P2657】[SCOI2009]windy数 – 洛谷、BZOJ：Problem 1026. — [SCOI2009]windy数

题目描述

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？

输入输出格式

输入格式：
包含两个整数，A B。

输出格式：
一个整数

输入输出样例

输入样例#1：

1 10

输出样例#1：

9

输入样例#2：

25 50

输出样例#2：

20

说明

100%的数据，满足 1 <= A <= B <= 2000000000 。

题解

很简单的数位DP，直接套路用上去，判一下差是否不小于2即可。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 50;

LL a, b, num[MAXN], dp[MAXN][MAXN][2][2];

inline LL dfs(int step, int lst, bool zero, bool lim) {
    if(!step) return !zero;
    if(dp[step][lst][zero][lim] != -1) return dp[step][lst][zero][lim];
    int limm = lim ? num[step] : 9, res = 0;
    for(int i = 0; i <= limm; i++) {
        if(abs(lst - i) < 2 && !zero) continue;
        res += dfs(step - 1, i, zero && !i, lim && i == num[step]);
    }
    return dp[step][lst][zero][lim] = res;
}

inline LL cal(LL x) {
    int n = 0;
    while(x) {
        num[++n] = x % 10; x /= 10;
    }
    LL res = 0;
    for(int i = 0; i <= num[n]; i++) {
        res += dfs(n - 1, i, i == 0, i == num[n]);
    }
    return res;
}

int main() {
    memset(dp, -1, sizeof(dp));
    a = readint(); b = readint();
    printf("%lld", cal(b) - cal(a - 1));
    return 0;
}