HDU_1502_dp

Regular Words

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2102 Accepted Submission(s): 825

Problem Description

Consider words of length 3n over alphabet {A, B, C} . Denote the number of occurences of A in a word a as A(a) , analogously let the number of occurences of B be denoted as B(a), and the number of occurenced of C as C(a) .

Let us call the word w regular if the following conditions are satisfied:

A(w)=B(w)=C(w) ;
if c is a prefix of w , then A(c)>= B(c) >= C(c) .
For example, if n = 2 there are 5 regular words: AABBCC , AABCBC , ABABCC , ABACBC and ABCABC .

Regular words in some sense generalize regular brackets sequences (if we consider two-letter alphabet and put similar conditions on regular words, they represent regular brackets sequences).

Given n , find the number of regular words.

Input

There are mutiple cases in the input file.

Each case contains n (0 <= n <= 60 ).

There is an empty line after each case.

Output

Output the number of regular words of length 3n .

There should be am empty line after each case.

Sample Input

Sample Output

还是看题解做的，蓝瘦。。。

dp[i][j][k][100]; i这维表示a的个数，j这维表示b的个数，k这维表示c的个数。

dp过程中需要用大数加法。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;



void add(char A[],char B[],char C[])
{
    int a=0;
    int len1=strlen(A);
    int len2=strlen(B);
    int wei=0;
    while(a<len1&&a<len2)
    {
        int sum=A[a]+B[a]-'0'-'0'+wei;
        wei=0;
        if(sum>9)
        {
            wei++;
            sum-=10;
        }
        C[a]=sum+'0';
        a++;
    }
    while(a<len1)
    {
        int sum=A[a]+wei-'0';
        wei=0;
        if(sum>9)
        {
            wei++;
            sum-=10;
        }
        C[a]=sum+'0';
        a++;
    }
    while(a<len2)
    {
        int sum=B[a]+wei-'0';
        wei=0;
        if(sum>9)
        {
            wei++;
            sum-=10;
        }
        C[a]=sum+'0';
        a++;
    }
    if(wei>0)
        C[a++]='1';
    C[a]='';
}

char dp[65][65][65][105];

int main()
{
    char A[1005],B[1005],C[1005];
    for(int i=0; i<=60; i++)
        for(int j=0; j<=60; j++)
            for(int k=0; k<=60; k++)
                strcpy(dp[i][j][k],"0");
    strcpy(dp[0][0][0],"1");

    for(int i=1; i<=60; i++)
        for(int j=0; j<=60; j++)
            for(int k=0; k<=60; k++)
            {
                if(i>=j&&j>=k)
                {
                    add(dp[i-1][j][k],dp[i][j-1][k],dp[i][j][k]);
                    add(dp[i][j][k],dp[i][j][k-1],dp[i][j][k]);
                }
            }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int len=strlen(dp[n][n][n]);
        char res[105];
        for(int i=len-1;i>=0;i--)
            res[len-i-1]=dp[n][n][n][i];
        res[len]='';
        printf("%s

",res);
        //getchar();
    }
    return 0;
}