「HDU 2089」不要 62 - 数位 DP

发表于 | 分类于

不吉利的数字为所有含有 或 的号码。例如： 都属于不吉利号码。但是， 虽然含有 和 ，但不是 连号，所以不属于不吉利数字之列。

你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

链接

HDU 2089

题解

数位 DP，设

表示号码的最后 位，这 位的上一个字符是 ，之前的字符是否全部紧贴上界，的总数量。

每次枚举这 位的最高位，特判 ，特判连续的 即可。

代码

#include <cstdio>
#include <cstring>

const int MAXX = 1000000;
const int MAXN = 7;
const int CHARSET_SIZE = 10;
const int FLAG = 2;

int a[MAXN], n;

int mem[MAXN + 1][CHARSET_SIZE][FLAG];
bool calced[MAXN + 1][CHARSET_SIZE][FLAG];

inline int dp(const int n, const int last, const bool flag) {
    int &ans = mem[n][last][flag];
    if (calced[n][last][flag]) return ans;
    calced[n][last][flag] = true;

    if (n == 0) {
        ans = 1;
    } else {
        int limit;
        if (flag) limit = a[::n - n];
        else limit = CHARSET_SIZE - 1;

        for (int i = 0; i <= limit; i++) {
            if (last == 6 && i == 2 || i == 4) continue;
            ans += dp(n - 1, i, flag && i == limit);
        }
    }

    // printf("dp(%d, %d) = %d\n", n, last, ans);
    return ans;
}

inline int solve(const int x) {
    char s[MAXN + 1];
    sprintf(s, "%d", x);
    n = strlen(s);
    for (int i = 0; i < n; i++) a[i] = s[i] - '0';

    memset(mem, 0, sizeof(mem));
    memset(calced, 0, sizeof(calced));

    int ans = 0;
    for (int i = 0; i <= a[0]; i++) {
        if (i == 4) continue;
        ans += dp(n - 1, i, i == a[0]);
        // printf("[%d, %d] -> %d\n", n - 1, i, dp(n - 1, i, i == a[0]));
    }

    return ans;
}

int main() {
    int l, r;
    while (scanf("%d %d", &l, &r), !(l == 0 && r == 0)) {
        printf("%d\n", solve(r) - solve(l - 1));
    }

    return 0;
}