【解题报告】[动态规划] RQNOJ

原题地址：http://www.rqnoj.cn/problem/38

解题思路：

　　状态表示：dp[i][j][k]表示i个A，j个B，k个C组成的满足条件的字符串的个数

　　初始状态：dp[0][0][0]=1。

　　状态转移方程：dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k-1] 其中要满足i>j>k>0。

　要注意的是，答案非常大，要用大数模板。。。Orz

　大数模板就不贴了，就贴动态规划的部分：

部分代码：

 1 BigNum dp[65][65][65];
 2 int d()
 3 {
 4     int i,j,k;
 5     for(i=0;i<=60;i++)
 6     for(j=0;j<=60;j++)
 7     for(k=0;k<=60;k++)
 8         dp[i][j][k]=0;
 9     dp[0][0][0]=1;
10     for(i=0;i<=60;i++)
11         for(j=0;j<=60;j++)
12             for(k=0;k<=60;k++)
13     {
14         if(i>j) dp[i][j][k]=dp[i][j][k]+dp[i-1][j][k];
15         if(j>k) dp[i][j][k]=dp[i][j][k]+dp[i][j-1][k];
16         if(k>0) dp[i][j][k]=dp[i][j][k]+dp[i][j][k-1];
17     }
18     return 1;
19 }
20 int main()
21 {
22     int N;
23     d();
24     cin>>N;
25     cout<<dp[N][N][N]<<endl;
26     return 0;
27 }

View Code