POJ 3071 题目解答:有 2^n 支球队,每两支队伍比一次,求最后胜出概率最大的球队。
解题思路:
设 d[i][j] 为第 i 场 第 j 支球队胜出,那么前提条件是,第 j 支球队和对手第 k 支球队都获胜了前 i-1 场并且在这一场 j 胜出了
- d[i][j]+=d[i-1][j]*d[i-1][k]*p[j][k];
那么问题就在于,因为每次两支队伍是相邻的,如何找第 j 支球队的对手?
这里用到一个异或运算方法:
当 j 为奇数的时候,j=(2n+1) 那么 j 的对手必定是(2n) 即 (2n+1)^1==2n
同理当 j 为偶数的时候,j=2n 此时 j 的对手为 (2n+1) 即 (2n)^1=2n+1
- #include#include#includeusing namespace std;#define M(1 << 7) + 10double p[M][M],
- dp[M][M];
- int bit(int x) //位运算求出2的x次方 { return 1<>(i-1))^1)==(k>>(i-1))) //(2n)^1=2n+1 (2n+1)^1=2n dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k]; int p=0; for(int i=0;idp[n][p]) p=i; printf("%d\n",p+1); } return 0;}
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/03-17/18933542.html