POJ 2711 Regular Words（DP + 高精度）

题目链接：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也可以。

代码如下：

 1 # include<iostream>
 2 # include<cstdio>
 3 # include<cstring>
 4 using namespace std;
 5 
 6 short dp[61][61][61][81];
 7 void init()
 8 {
 9     short i,j,k,p,temp;
10     memset(dp,0,sizeof(dp));
11     dp[0][0][0][0] = 1;
12     for(i=0; i<=60; i++)
13         for(j=i; j<=60; j++)
14             for(k=j; k<=60; k++)
15             {
16                 if(i>0)     //dp[i][j][k] += dp[i-1][j][k];
17                 {
18                     temp = 0;
19                     for(p=0; p<=80; p++)
20                     {
21                         dp[i][j][k][p] += dp[i-1][j][k][p] + temp;
22                         if(dp[i][j][k][p]>9)
23                         {
24                             temp = 1;
25                             dp[i][j][k][p] -= 10;
26                         }
27                         else
28                             temp = 0;
29                     }
30                 }
31                 if(j>0) //dp[i][j][k] += dp[i][j-1][k];
32                 {
33                     temp = 0;
34                     for(p=0; p<=80; p++)
35                     {
36                         dp[i][j][k][p] += dp[i][j-1][k][p] + temp;
37                         if(dp[i][j][k][p]>9)
38                         {
39                             temp = 1;
40                             dp[i][j][k][p] -= 10;
41                         }
42                         else
43                             temp = 0;
44                     }
45                 }
46                 if(k>0) //dp[i][j][k] += dp[i][j][k-1];
47                 {
48                     temp = 0;
49                     for(p=0; p<=80; p++)
50                     {
51                         dp[i][j][k][p] += dp[i][j][k-1][p] + temp;
52                         if(dp[i][j][k][p]>9)
53                         {
54                             temp = 1;
55                             dp[i][j][k][p] -= 10;
56                         }
57                         else
58                             temp = 0;
59                     }
60                 }
61             }
62 }
63 
64 int main()
65 {
66     init();
67     int n;
68     while(scanf("%d",&n)!=EOF)
69     {
70         int i;
71         for(i=80; i>=0; i--)
72             if(dp[n][n][n][i] != 0) break;  
73         for(; i>=0; i--)    //输出高精度数
74             printf("%d",dp[n][n][n][i]);
75         printf("

");
76     }
77     return 0;
78 }