?

大意：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 
  
   
#include 
   
     int n; double p[1000][1000]; double dp[10][1000]; int main() { while(~scanf(%d, &n) && n != -1){ for(int i = 0; i < (1<
    
     >(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<
     
       ans){ ans = dp[n][i]; Ans = i; } } printf(%d , Ans+1); } return 0; }
     
    
   
  

?