poj1322Chocolate<DP>

链接:http://poj.org/problem?id=1322

题意:

C 种不同颜色的巧克力，每种巧克力同样多，把巧克力一个一个拿到桌子上，当发现有相同颜色就全吃掉，求取出了 n 个后，还剩 m 个在桌子的概率;

思路:

典型的动态规划; 状态转移方程: dp[n][m]=dp[n-1][m-1]*p1+dp[n-1][m+1]*p2; p1=(c-m+1)/c,p2=(m+1)/c;

可是时间复杂度为n*c = 1e8 ; 果断TLE; 后来在黑书上看到解题方法为生成函数, 去百度未果, 却看到犀利减枝 if(n>1000) n=1000+n%2 ;

还有G++各种wa,换c++ 果断 ac, 各种不靠谱;

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 double dp[2][102];
 7 
 8 int main()
 9 {
10     int c, n, m, i, j;
11 
12     while(scanf("%d", &c) && c)
13     {
14         scanf("%d %d", &n, &m);
15         if(m > n || m > c || (m + n) % 2){
16             printf("0.000\n");
17             continue;
18         }
19         if(n > 1001)
20             n = n % 2 ? 1001 : 1000;
21         
22         memset(dp, 0, sizeof(dp));
23         dp[0][0] = 1.0;
24         for(i = 1; i <= n; i++){
25             for(j = 0; j <= i && j <= c; j++){
26                 dp[i%2][j] = 0.0;
27                 if((i + j) % 2) continue;
28                 if(j > 0)
29                     dp[i%2][j] += dp[1-i%2][j-1] * ((c-j+1.0)*1.0/c);
30                 if(j+1 <= i-1)
31                     dp[i%2][j] += dp[1-i%2][j+1] * ((j+1.0)*1.0/c);
32             }
33         }
34         printf("%.3lf\n", dp[n%2][m]);
35     }
36     return 0;
37 }