题意：
有2*n只队伍参加n论的淘汰赛，给出任意两只队伍交战的各自的胜率，求最后剩下概率最高的队伍。
分析：
概率dp,dp[i][j]表示第i轮结束后队伍j还在场上的概率，dp[i][j]=dp[i-1][j]*sum(dp[i-1][k]p[j][k])(1<=k<=2^n,且k有可能在第i轮同j交战)，关键是怎么表示k有可能在第i轮同j交战，这里用的是(j-1)>>i==(k-1)>>i&&(j-1)>>(i-1)!=(k-1)>>(i-1)，把每个队的id用二进制写出来画画图就知道为什么这样喽。
代码：
//poj 3071//sep9#include <iostream>using namespace std;const int maxN=128;double p[maxN+10][maxN+10];double dp[maxN+10][maxN+10];int main(){int n;while(scanf("%d",&n)==1&&n!=-1){for(int i=1;i<=(1<<n);++i)for(int j=1;j<=(1<<n);++j)scanf("%lf",&p[i][j]);for(int i=1;i<=(1<<n);++i)dp[0][i]=1.0;for(int i=1;i<=n;++i)for(int j=1;j<=(1<<n);++j){double sum=0;for(int k=1;k<=(1<<n);++k)if((j-1)>>i==(k-1)>>i&&(j-1)>>(i-1)!=(k-1)>>(i-1))sum+=dp[i-1][k]*p[j][k];dp[i][j]=dp[i-1][j]*sum;}double maxx=-1.0;int idx;/*for(int i=1;i<=n;++i){for(int j=1;j<=(1<<n);++j)printf("%.3lf ",dp[i][j]);printf("\n");}*/for(int i=1;i<=(1<<n);++i){if(maxx<dp[n][i]){maxx=dp[n][i];idx=i;}}printf("%d\n",idx);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，不要轻言放弃，否则对不起自己
