Poj 3071 Football (比赛对阵概率DP)

灰太狼 2022-08-27 03:39 63阅读 0赞

题意：2^n个队进行足球赛，给出队伍间比赛获胜概率的矩阵。求最后胜利的概率最大的是哪只球队。

思路：这题最关键的是找出每轮对阵队伍标号间的关系。

设i表示比赛正在进行第几轮，j,k为一组比赛的队伍，假设球队从0开始编号并用二进制表示， 000,001,010,011,100,101,110,111,共8组，则：

第一轮 000-001,010-011,100-101,110-111  
第二轮（（000,001）-（010,011））-（（100,101）-（110,111））  
第三轮（（000,001,010,011）-（100,101,110,111））  
  
可以得出规律：在第i轮，满足如下关系j,k就可能对阵  
(j>>(i-1))^1==k>>(i-1)

用dp\[i\]\[j\] 表示第i轮比赛时j获胜的概率。则状态转移方程：  
dp\[i\]\[j\] = dp\[i-1\]\[j\]\*dp\[i-1\]\[k\]\*p\[j\]\[k\]

#include <cstdio>
    #include <cstring>
    
    const int N=135;
    
    double dp[10][N];  //dp[i][j] 表示第i轮比赛时j获胜的概率。
    double p[N][N];
    
    int main ()
    {
    	int n,i,j;
    	while (scanf("%d",&n) ,~n)
    	{
    		int m=1<<n;
    		for (i=0;i<m;i++)
    			for (j=0;j<m;j++)
    				scanf("%lf",&p[i][j]);
    		memset(dp,0,sizeof(dp));
    		for (i=0;i<m;i++)
    			dp[0][i]=1;
    		for (i=1;i<=n;i++)
    			for (j=0;j<m;j++)
    				for (int k=0;k<m;k++)
    					if(((j>>(i-1))^1)==(k>>(i-1)))
    						dp[i][j] += dp[i-1][j]*dp[i-1][k]*p[j][k];
    		double maxp=0;
    		int ans;
    		for (i=0;i<m;i++)
    			if (dp[n][i]>maxp)
    			{
    				maxp=dp[n][i];
    				ans=i+1;
    			}
    		printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，63人围观）

还没有评论，来说两句吧...

相关阅读

相关概率期望dp

简易的入门：http://kicd.blog.163.com/blog/static/126961911200910168335852/ 大神的总结：http://blog

港控/mmm°/ 2023年08月17日 16:25/ 0 赞/ 77 阅读

相关 POJ 3744-Scout YYF I【概率DP+矩阵快速幂】

题意：有n个地方有地雷，给出来你下标，对于每个位置i, 你走到i+1的概率是p，走到i+2的概率是1-p，问你不被地雷炸的概率。思路：这题转移方程很好想，就是f\[i\]

迈不过友情╰/ 2023年06月02日 15:56/ 0 赞/ 92 阅读

相关烟花（概率dp）

https://ac.nowcoder.com/acm/problem/18200 分析： double x = 1.0000 - arr\[i\]; doubl

秒速五厘米/ 2023年01月13日 15:56/ 0 赞/ 175 阅读

相关 Poj 3071 Football (比赛对阵概率DP)

题意：2^n个队进行足球赛，给出队伍间比赛获胜概率的矩阵。求最后胜利的概率最大的是哪只球队。思路：这题最关键的是找出每轮对阵队伍标号间的关系。设i表示比赛正在进行第几轮

灰太狼/ 2022年08月27日 03:39/ 0 赞/ 64 阅读

相关 POJ 3744 Scout YYF I （矩阵相乘+概率DP）

POJ 3744 Scout YYF I （矩阵相乘+概率DP）：[http://poj.org/problem?id=3744][http_poj.org_problem_i

￡神魔★判官ぃ/ 2022年08月21日 12:00/ 0 赞/ 66 阅读

相关 POJ 3071 Football （概率DP）

POJ 3071 Football （概率DP）：[http://poj.org/problem?id=3071][http_poj.org_problem_id_3071]

绝地灬酷狼/ 2022年08月21日 11:59/ 0 赞/ 109 阅读

相关 poj2096 概率dp入门

题意：一个系统有s个子系统，一共会产生n中bug。某人一天可以发现一个bug，这个bug属于一个子系统，属于一个种类，每个bug属于某个子系统的概率是1/s,属于某个分类的

我就是我/ 2022年08月20日 15:16/ 0 赞/ 143 阅读

相关 NIMK博弈游戏，POJ-2315 Football Game

普通的NIM游戏是在n堆石子中每次选一堆，取任意个石子，而NIMK游戏是在n堆石子中每次选择k堆，1<=k<=n，从这k堆中每堆里都取出任意数目的石子，取的石子数可以不同，其他

淩亂°似流年/ 2022年06月10日 10:07/ 0 赞/ 207 阅读

相关 poj3744（概率dp+矩阵快速幂）

<table style="background-image:url("http://poj.org/images/table_back.jpg");fon

女爷i/ 2022年05月30日 12:28/ 0 赞/ 192 阅读

相关 Poj 1644 To Bet or Not To Bet (概率 DP)

题意：棋盘是一个线性表，初始位置0，结束位置m+1，每一轮抛硬币决定向右一步还是两步，概率各为0.5。棋盘每格上都会有一个说明+n，-n，L，或者 0，分别意味着向右走n格，向

傷城~/ 2021年11月01日 14:46/ 0 赞/ 187 阅读