概率DP
kuangbin总结中的第10题
简单的画个比赛图，会发现是一颗完全二叉树，且同一层的子树之间各自独立，只有在合并得到更高一层结果时才结合。
所以我们可以按比赛轮数进行DP，f[i][j]表示第 i 轮之后第 j 个球队没有被淘汰的概率，仔细一想可以发现：首先这支球队得在第 i-1 轮中胜出，然后他在第 i 轮中的对手的可能情况即是在比赛图二叉树中的「兄弟」结点代表的那2^(i-1)支球队，这个“兄弟”可以用异或快速求出。
这样逐层递推，避免了许多无用的状态枚举，每层要枚举 2^i 支球队，以及第 i 支球队的2^(i-1)个可能的对手，所以复杂度为O(n* 2^2n)
//POJ 3071
#include<cmath>
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
const int N=<<;
double p[N][N],f[][N];
int main(){
#ifndef ONLINE_JUDGE
freopen("3071.in","r",stdin);
freopen("3071.out","w",stdout);
#endif
int n,m;
while(scanf("%d",&n)!=EOF && n!=-){
m=<<n;
rep(i,m) rep(j,m) scanf("%lf",&p[i][j]); rep(j,m) f[][j]=1.0;
F(i,,n) rep(j,m){
int t=j/(<<(i-));
t^=;
f[i][j]=;
for(int k=t*(<<(i-)); k<t*(<<(i-))+(<<(i-));k++)
f[i][j]+=f[i-][j]*f[i-][k]*p[j][k];
}
int ans;
double tmp=;
rep(i,m)
if (f[n][i]>tmp){
ans=i;
tmp=f[n][i];
}
printf("%d\n",ans+);
}
return ;
}