HDU 5642 – King’s Order [数位DP]

Link

传送门

Problem

After the king’s speech , everyone is encouraged. But the war is not over. The king needs to give orders from time to time. But sometimes he can not speak things well. So in his order there are some ones like this: “Let the group-p-p three come to me”. As you can see letter ‘p’ repeats for 3 times. Poor king!

Now , it is war time , because of the spies from enemies , sometimes it is pretty hard for the general to tell which orders come from the king. But fortunately the general know how the king speaks: the king never repeats a letter for more than 3 times continually .And only this kind of order is legal. For example , the order: “Let the group-p-p-p three come to me” can never come from the king. While the order:” Let the group-p three come to me” is a legal statement.

The general wants to know how many legal orders that has the length of n

To make it simple , only lower case English Letters can appear in king’s order , and please output the answer modulo 1000000007.

We regard two strings are the same if and only if each charactor is the same place of these two strings are the same.

Mean

国王演讲后士气大增,但此时战争还没有结束,国王时不时要下发命令。由于国王的口吃并没有治愈,所以传令中可能出现:“让第三军-军-军,到前线去” 这样的命令。由于大洋国在军队中安插了间谍 , 战事紧急,很多时候前线的指挥官不能分清哪些命令真正来自国王。但国王的命令有一个特点,他每次连续重复的字符最多 33 次. 所以说他的命令中没有:“让第三军-军-军-军 , 到前线去”,但是可以有 :“让第三军-军 , 到前线去” 。 此时将军找到了你,你需要告诉他,给定命令的长度长度为 nn,有多少种不同的命令可以是国王发出的 。(也就是求长度为 nn 的合格字符串的个数)当然,国王可能说出一句话没有犯任何口吃,就像他那次演讲一样。 为了简化答案,国王的命令中只含有小写英文字母,且对答案输出模 10000000071000000007。 我们认为两个命令如果完全相同那么这两个字符串逐个比较就完全相同。

Analysis

数一个长度为 n 的序列 , 并且序列中不能出现长度大于 3 的连续的相同的字符。数位DP~

dp[i][j]表示长度为i,最后字符长度为j的合法串。每次把当前串后面加一个字符递推即可。

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2048;
const ll mod = 1000000007;
ll dp[maxn][5];

void init() {
    dp[1][1] = 26;
    for(int i = 1; i <= 2000; ++i) {
        for(int j = 1; j <= 3; ++j) {
            if(!dp[i][j]) continue;
            if(j < 3) dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % mod;
            dp[i+1][1] = (dp[i+1][1] + dp[i][j] * 25) % mod;
        }
    }
}

int main() {
    init();
    int T; scanf("%d", &T);
    while(T--) {
        int n; scanf("%d", &n);
        ll ans = 0;
        for(int i = 1; i <= 3; ++i)
            ans = (ans + dp[n][i]) % mod;
        printf("%I64d\n", ans);
    }
    return 0;
}

欢迎留言