首页 > 代码库 > poj 3071 Football (概率dp)

poj 3071 Football (概率dp)

2024-07-07 04:21:24   231人阅读

题目链接

没大做过概率dp的题目，这题只看了一下别人的d[][]数组的定义，剩下的自己想了一会写的，居然1A。

题意：给定2^n行， 2^n列，i行j列代表第i 个人赢第j个人的概率，求经过n局，哪个人赢的概率最大，

比赛规则是相邻的人先比，赢的人进入下一局再与赢的相邻的人比，输的直接淘汰。

分析：d[i][j]代表第j个人，第i局赢的概率。d[i][j]  += d[i-1][j]*d[i-1][k]*p[j][k];

k是取相邻另一组的所有人。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 const int maxn = 150;
 7 double p[maxn][maxn], d[maxn][maxn];
 8 
 9 int main()
10 {
11     int n, i, j, k, sum, ans, l, r, x, y;
12     double Max;
13     while(~scanf("%d", &n) && n!=-1)
14     {
15         sum = pow(2, n);
16         memset(d, 0, sizeof(d));
17         for(i = 1; i <= sum; i++)
18             for(j = 1; j <= sum; j++)
19                 scanf("%lf", &p[i][j]);
20         for(j = 1; j <= sum; j++)
21             if(j&1)
22                 d[1][j] = p[j][j+1];
23             else
24                 d[1][j] = p[j][j-1];
25 
26         for(i = 2; i <= n; i++)
27             for(j = 1; j <= sum; j++)
28             {
29                 x = pow(2, i-1);
30                 y = (j-1)/x;
31                 if(y&1)
32                 {
33                     r = x*y + 1;  //用l和r计算当前的人和相邻的另外一组的比赛
34                     l = r - x;
35                 }
36                 else
37                 {
38                     l = (y+1)*x + 1;
39                     r = l+x;
40                 }
41                 for(k = l; k < r; k++)
42                 if(j != k)
43                 d[i][j] += d[i-1][j]*d[i-1][k]*p[j][k];
44             }
45         ans = 1; Max = d[n][1];
46         for(j = 1; j <= sum; j++)
47         if(d[n][j] > Max)
48         {
49             Max = d[n][j];
50             ans = j;
51         }
52         cout<<ans<<endl;
53     }
54     return 0;
55 }

 


联系
我们