学步园

题意：2^n个球队比赛，0和1比，2和3比，以此类推，循环比下去，直至只剩下一个队伍，问那个队伍的冠军的的概率最大 ？

p【i】【j】为i打败j的概率

解析：dp【i】【j】为第i场比赛j胜利的概率 ，则dp【n】【j】的最大值就是答案j  

这题的关键是枚举，把球队比赛化成一棵二叉树，每次两个节点比

#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
using namespace std;

#define N 200
int main()
{
    int i,k,t,j,n,m,maxnum;
    double p[N][N],dp[9][N],maxp;
    while(scanf("%d",&n)&&(n!=-1))
    {
        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(k=0;k<m;k++) //还可以化简的、、、、、
               {
                  if((j>>(i-1))==(k>>(i-1)^1))
                    dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k];
               }
            }
        }
        maxp=0;
        maxnum=0;
        for(j=0; j<m; j++)
        {
            if(dp[n][j]>maxp)
            {
                maxp=dp[n][j];
                maxnum=j;
            }
        }
        printf("%d\n",maxnum+1);
    }
    return 0;
}