POJ 3071 Football(概率DP)

不1Y都对不住看过那么多年的球。dp[i][j]表示i队进入第j轮的概率,此题用0-1<<n表示非常方便。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 double dp[501][501];
 8 double p[501][501];
 9 int main()
10 {
11     int n,i,j,mod,c,k,ans;
12     double maxz;
13     while(scanf("%d",&n)!=EOF)
14     {
15         if(n < 0) break;
16         for(i = 0;i < (1<<n);i ++)
17         {
18             for(j = 0;j < (1<<n);j ++)
19             {
20                 scanf("%lf",&p[i][j]);
21             }
22         }
23         for(i = 0;i < (1<<n);i ++)
24         {
25             dp[0][i] = 1;
26         }
27         for(i = 1;i <= n;i ++)
28         {
29             for(j = 0;j < (1<<n);j ++)
30             dp[i][j] = 0;
31         }
32         for(i = 1;i <= n;i ++)
33         {
34             for(j = 0;j < (1<<n);j ++)
35             {
36                 mod = j%(1<<i);
37                 if(mod >= (1<<(i-1)))
38                 {
39                     c = (j/(1<<i))*(1<<i);
40                     for(k = 0;k < (1<<(i-1));k ++)
41                     {
42                         dp[i][j] += dp[i-1][j]*dp[i-1][c+k]*p[j][c+k];
43                     }
44                 }
45                 else
46                 {
47                     c = (j/(1<<i))*(1<<i)+(1<<(i-1));
48                     for(k = 0;k < (1<<(i-1));k ++)
49                     {
50                         dp[i][j] += dp[i-1][j]*dp[i-1][c+k]*p[j][c+k];
51                     }
52                 }
53             }
54         }
55         ans = 0;maxz = 0;
56         for(i = 0;i < (1<<n);i ++)
57         {
58             if(maxz < dp[n][i])
59             {
60                 ans = i;
61                 maxz = dp[n][i];
62             }
63         }
64         printf("%d
",ans+1);
65     }
66     return 0;
67 }