首页 > 代码库 > POJ 3071 Football(简单 概率DP)
POJ 3071 Football(简单 概率DP)
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)时,表明两个子节点是竞争关系,胜利者将更新到复接点。
#include <stdio.h> #include <string.h> int n; double p[1000][1000]; double dp[10][1000]; int main() { while(~scanf("%d", &n) && n != -1){ for(int i = 0; i < (1<<n); ++i){ for(int j = 0; j < (1<<n); ++j){ scanf("%lf", &p[i][j]); } } memset(dp, 0, sizeof(dp)); for(int i = 0; i < (1<<n); ++i){ dp[0][i] = 1; } for(int i = 1; i <= n; ++i){ for(int j = 0; j < (1<<n); ++j){ for(int k = 0; k < (1<<n); ++k){ if(((j>>(i-1))^1) == (k>>(i-1))) dp[i][j] += dp[i-1][k]*dp[i-1][j]*p[j][k]; } } } double ans = -1; int Ans = -1; for(int i = 0; i < (1<<n); ++i){ if(dp[n][i] > ans){ ans = dp[n][i]; Ans = i; } } printf("%d\n", Ans+1); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。