「HDU 5462」King's Order - 数位 DP

由于国王的口吃并没有治愈,所以传令中可能出现:“让第三军-军-军,到前线去”这样的命令。由于大洋国在军队中安插了间谍,战事紧急,很多时候前线的指挥官不能分清哪些命令真正来自国王。但国王的命令有一个特点,他每次连续重复的字符最多 3 次. 所以说他的命令中没有:“让第三军-军-军-军,到前线去”,但是可以有:“让第三军-军,到前线去”。

此时将军找到了你,你需要告诉他,给定命令的长度长度为 n ,有多少种不同的命令可以是国王发出的。(也就是求长度为 n 的合格字符串的个数)当然,国王可能说出一句话没有犯任何口吃,就像他那次演讲一样。

链接

HDU 5642

题解

数位 DP,设

f[n][f1][f2][f3][lastChar]

表示长度为 n 的字符串,最后四个字符中两两是否相等,最后一个字符是 lastChar ,状态转移时,枚举最后一个字符,如果三个标志位均为真,则状态非法,答案为零。

每次不需要重新计算,利用之前计算过的值即可。

代码

#include <cstdio>
#include <cstring>

const int MAXT = 10;
const int MAXN = 2000;
const int MOD = 1000000007;
const int CHARSET_SIZE = 26;

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

inline int dp(const int n, const bool c2EqualToC1, const bool c3EqualToC2, const bool c4EqualToC3, const int c4) {
    int &ans = mem[n][c2EqualToC1][c3EqualToC2][c4EqualToC3][c4];
    if (calced[n][c2EqualToC1][c3EqualToC2][c4EqualToC3][c4]) return ans;
    calced[n][c2EqualToC1][c3EqualToC2][c4EqualToC3][c4] = true;

    if (c2EqualToC1 && c3EqualToC2 && c4EqualToC3) {
        ans = 0;
    } else if (n == 0) {
        ans = 1;
    } else {
        ans = 0;
        for (int i = 0; i < CHARSET_SIZE; i++) {
            ans += dp(n - 1, c3EqualToC2, c4EqualToC3, i == c4, i);
            ans %= MOD;
        }
    }

    return ans;
}

// inline void cleanUp() {
//     memset(mem, 0, sizeof(mem));
//     memset(calced, 0, sizeof(calced));
// }

int main() {
    int t;
    scanf("%d", &t);

    while (t--) {
        int n;
        scanf("%d", &n);

        printf("%d\n", dp(n, false, false, false, CHARSET_SIZE));

        // cleanUp();
    }

    return 0;
}