题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1711
题目大意：给定一个正整数n，产生一个3*n位长的串，要求这个串中（1）A、B、C的数目都是n；（2）这个串的任意一个前缀，也就是从开始往后任意一段连续序列中字符的个数A>=B>=C。求满足条件的数目。
Sample Input
2 3
Sample Output
5 42
分析：令dp[i][j][k] 表示从第一个字符开始，长度为i+j+k的串，A的个数为 i ，B的个数为 j ，C的个数为 k 的字符串的个数。
则如果i>=j>=k 则可以根据最后一个字符是A, B还是C，分三类计数，假设是最后一位是A，由于题目的要求是前缀 ,所以前面的放法数恰好是dp[i-1][j][k]
另外两种情况同理，加的时候注意下标小于零就不要了，答案为dp[n][n][n]
后来发现是高精度，需要再加一维dp[i][j][k][p]，最后一维是该数字的大数表示。
这样如果dp数组用int类型表示，会超内存。后来改用short类型，内存36000险过，用char类型也是可以过的。short型理论上用输出%hd的，不过%d也可以。
代码如下：
# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std; short dp[][][][];
void init()
{
short i,j,k,p,temp;
memset(dp,,sizeof(dp));
dp[][][][] = ;
for(i=; i<=; i++)
for(j=i; j<=; j++)
for(k=j; k<=; k++)
{
if(i>) //dp[i][j][k] += dp[i-1][j][k];
{
temp = ;
for(p=; p<=; p++)
{
dp[i][j][k][p] += dp[i-][j][k][p] + temp;
if(dp[i][j][k][p]>)
{
temp = ;
dp[i][j][k][p] -= ;
}
else
temp = ;
}
}
if(j>) //dp[i][j][k] += dp[i][j-1][k];
{
temp = ;
for(p=; p<=; p++)
{
dp[i][j][k][p] += dp[i][j-][k][p] + temp;
if(dp[i][j][k][p]>)
{
temp = ;
dp[i][j][k][p] -= ;
}
else
temp = ;
}
}
if(k>) //dp[i][j][k] += dp[i][j][k-1];
{
temp = ;
for(p=; p<=; p++)
{
dp[i][j][k][p] += dp[i][j][k-][p] + temp;
if(dp[i][j][k][p]>)
{
temp = ;
dp[i][j][k][p] -= ;
}
else
temp = ;
}
}
}
} int main()
{
init();
int n;
while(scanf("%d",&n)!=EOF)
{
int i;
for(i=; i>=; i--)
if(dp[n][n][n][i] != ) break;
for(; i>=; i--) //输出高精度数
printf("%d",dp[n][n][n][i]);
printf("\n\n");
}
return ;
}