首页 > 代码库 > POJ 3071 Football（简单 概率DP）

POJ 3071 Football（简单 概率DP）

2024-07-17 05:49:50   220人阅读

Football

 

原文链接：http://blog.csdn.net/xuechelingxiao/article/details/38520105

 

大意：2^n 个球队进行单场淘汰赛，每两只球队之间比赛会有胜负的概率，问最后谁夺冠的概率最大。

 

思路：简单的概率DP问题，主要是怎么处理哪两个球队比赛的问题。

DP方程为 dp[i][j] = ∑(dp[i-1][j]*dp[i-1][k]*p[j][k]); //dp[i][j]表示第 i 轮的时候，第 j 支队伍赢的概率。、

对于其中位运算，可以用一个二叉树来更直观的理解  (j>>(i-1))^1) 跟 (k>>(i-1)分别表示一个父节点的两个子节点， 当(j>>(i-1))^1) == (k>>(i-1)时，表明两个子节点是竞争关系，胜利者将更新到复接点。

 

 1 #include <stdio.h> 2 #include <string.h> 3  4 int n; 5 double p[1000][1000]; 6 double dp[10][1000]; 7  8 int main() 9 {10     while(~scanf("%d", &n) && n != -1){11         for(int i = 0; i < (1<<n); ++i){12             for(int j = 0; j < (1<<n); ++j){13                 scanf("%lf", &p[i][j]);14             }15         }16         memset(dp, 0, sizeof(dp));17 18         for(int i = 0; i < (1<<n); ++i){19             dp[0][i] = 1;20         }21         for(int i = 1; i <= n; ++i){22             for(int j = 0; j < (1<<n); ++j){23                 for(int k = 0; k < (1<<n); ++k){24                     if(((j>>(i-1))^1) == (k>>(i-1)))25                         dp[i][j] += dp[i-1][k]*dp[i-1][j]*p[j][k];26                 }27             }28         }29 30         double ans = -1;31         int Ans = -1;32         for(int i = 0; i < (1<<n); ++i){33             if(dp[n][i] > ans){34                 ans = dp[n][i];35                 Ans = i;36             }37         }38         printf("%d\n", Ans+1);39     }40 41     return 0;42 }
POJ 3071

 


联系
我们