程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu5642 King&#39;s Order（數位dp）

hdu5642 King&#39;s Order（數位dp）

編輯：C++入門知識

hdu5642 King's Order（數位dp）

King's Order

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 625Accepted Submission(s): 361
Problem Description 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.
Input The first line contains a number T(T≤10)

——The number of the testcases.

For each testcase, the first line and the only line contains a positive number n(n≤2000)

.
Output For each testcase, print a single number as the answer.
Sample Input

2 2 4
Sample Output

676 456950 hint: All the order that has length 2 are legal. So the answer is 26*26. For the order that has length 4. The illegal order are : "aaaa" , "bbbb"…….."zzzz" 26 orders in total. So the answer for n == 4 is 26^4-26 = 456950
Source BestCoder Round #75
題意：一個長度為n的字符串，每個字符不能連續出現3次以上（不包含3次）；求有多少種情況。分析：一道數位dp，很久沒做數位dp了，盡然完全不會了- -。

#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
using namespace std;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
#define ll long long
#define CL(a,b) memset(a,b,sizeof(a))
#define lson (i<<1)
#define rson ((i<<1)|1)
#define MAXN 100010

ll dp[2010][4];///dp[i][j]表示第i個位置，j表示當前連續字符出現了j次

int main()
{
    int T,n;
    cin>>T;
    dp[0][1] = 26;
    for(int i=1; i<2002; i++)
    {
        dp[i][2] = dp[i-1][1]%MOD;
        dp[i][3] = dp[i-1][2]%MOD;
        dp[i][1] = (dp[i-1][1]+dp[i-1][2]+dp[i-1][3])*25%MOD;
    }
    while(T--)
    {
        cin>>n;
        cout<<(dp[n-1][1]+dp[n-1][2]+dp[n-1][3])%MOD<