poj 3071 Football

题意：

给出一个n，现在有2的n次方个球队。

第一轮，1和2比，3和4比，5和6比。。。。

第二轮，先把胜出的按照序号从小到大排序，然后第一个和第二个比，第三个和第四个比。。。。

。。。。。

问那个队伍获得冠军的期望最大。

思路：

求概率，那么就顺序递推dp。

显然，比赛一共只有n轮，而且每一个队伍在每一轮中对决的队伍序号是有范围的。

比如第二轮，2只能和3，4比；3只能和1，2比。。。。

假设dp[i][j]表示第i个球队在第j轮比赛中获胜的概率，那么dp[i][j] = dp[i][j-1] * (Σ(dp[k][j-1] * p[i][k]))，k是有范围的，可以通过观察得出。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 double dp[1000][10];
 6 double p[1000][1000];
 7 int num[10];
 8 int main()
 9 {
10     int n;
11     num[0] = 1;
12     for (int i = 1;i < 10;i++) num[i] = 2 * num[i-1];
13     while (scanf("%d",&n) != EOF && ~n)
14     {
15         int m = num[n];
16         for (int i = 0;i < m;i++)
17         {
18             for (int j = 0;j < m;j++) scanf("%lf",&p[i][j]);
19         }
20         memset(dp,0,sizeof(dp));
21         for (int i = 0;i < m;i++)
22         {
23             if (i % 2)
24             {
25                 dp[i][1] = p[i][i-1];
26             }
27             else
28             {
29                 dp[i][1] = p[i][i+1];
30             }
31         }
32         for (int j = 2;j <= n;j++)
33         {
34             int cur = num[j-1];
35             for (int i = 0;i < m;i++)
36             {
37                 int id = i / cur;
38                 if (id % 2)
39                 {
40                     id--;
41                 }
42                 else
43                 {
44                     id++;
45                     
46                 }
47                 int l = id * cur;
48                 int r = l + cur;
49                 double tmp = 0;
50                 for (int k = l;k < r;k++)
51                 {
52                     tmp += dp[k][j-1] * p[i][k];
53                 }
54                 dp[i][j] = dp[i][j-1] * tmp;
55             }
56         }
57         int ans = 0;
58         for (int i = 1;i < m;i++)
59         {
60             if (dp[i][n] > dp[ans][n]) ans = i;
61         }
62         printf("%d
",ans+1);
63     }
64     return 0;
65 }