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

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

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

链接

HDU 5642

题解

数位 DP，设

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

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

代码

#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;
}