hdu1502 , Regular Words, dp,高精度加法

V - Regular Words

Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

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

2 3

Sample Output

5 42

一开始我以为只是简单的dp，感觉怎么这么简单啊，就随便写了一下提交了，然后就wa了，又检查了一下，觉得没什么问题，无奈只好求助于网上的题解，才知道原来是高精度加法，我就哭了! 我只写过杭电的1002，那和这里的高精度是一个档次的吗？估计了一下，这道题写了整整一天，各种改错，实在是没办法，问题太多了。。。。。。看来是字符串处理水平不足啊...话不多说，从dp的角度看，这道题其实不难，注意别超时，一开始用了四层for循环，180*60*60*60觉得不会超时，TLE了以后反应过来原来加法过程还要乘以一个数，这样就超时了，优化一下变成三重循环，这才勉强符合时限；因为没写过类似的高精度加法，所以写起来特别费力，字符串结束符号那里我估计是最让我蛋疼的地方，然后是一开始不知道怎么给字符串赋值，再就是我居然连高精度数都没搞清楚，还好学长提醒了我一下，这才少走了许多歪路，在这里感谢cxlove对我的提点，不然我估计就要写两天了。。。囧。。。

代码如下：

（代码写的有点搓，看来以后还得学点艺术啊。。。）

#include<stdio.h>
#include<string.h>
char dp[61][61][61][100];
void sum(char a[100],char b[100])
{
    long z=0,i=0,j=0;
    char c;
    while(a[i]!=''&&b[j]!='')
    {
        c=b[j];
        b[j]=(a[i]+b[j]-'0'-'0'+z)%10+48;
        z=(a[i]+c-'0'-'0'+z)/10;
        i++;
        j++;
    }
    if(a[i]!=''&&b[j]=='')
    {
        while(a[i]!='')
    {
        b[j]=(a[i]+z-'0')%10+48;
        z=(a[i]+z-'0')/10;
        i++;
        j++;
    }
    if(z!=0)
    {
        b[j]=z+'0';
        b[j+1]='';
    }
    else
        b[j]='';
    }
    else
    {
        while(a[i]==''&&b[j]!='')
    {
        c=b[j];
        b[j]=(b[j]+z-'0')%10+48;
        z=(c+z-'0')/10;
        j++;
    }
    if(z!=0)
    {
        b[j]=z+'0';
        b[j+1]='';
    }
    else
        b[j]='';
    }

}
    int max(long a,long b)
{
    return a>b?a:b;
}
int min(long a,long b)
{
    return a>b?b:a;
}
int main()
{
    long n,i,j,k,l,m;
    while(scanf("%ld",&n)!=EOF)
    {
        for(j=0; j<=n; j++)
            for(k=0; k<=n; k++)
                for(l=0; l<=n; l++)
                {
                    dp[j][k][l][0]='0';
                    dp[j][k][l][1]='';
                }
            for(j=1; j<=n; j++)
                for(k=0; k<=j; k++)
                    for(l=0; l<=k; l++)
                    {
                        if(k==0)
                        {
                            dp[j][k][l][0]='1';
                            dp[j][k][l][1]='';
                        }
                        else if(l==0)
                        {
                            sum(dp[j-1][k][l],dp[j][k][l]);
                            sum(dp[j][k-1][l],dp[j][k][l]);
                        }
                        else
                        {
                            sum(dp[j-1][k][l],dp[j][k][l]);
                            sum(dp[j][k-1][l],dp[j][k][l]);
                            sum(dp[j][k][l-1],dp[j][k][l]);
                        }
                    }
        l=strlen(dp[n][n][n]);
        for(j=l-1; j>=0; j--)
            printf("%c",dp[n][n][n][j]);
        printf("
");
        printf("
");
    }
    return 0;
}