学步园

题意是：有2^n支队伍，告诉你p【j】【k】表示j打败k的概率。求最后赢得比赛概率最大的队伍。

dp【i】【j】 表示在第i回合，j获胜的概率

此题需要注意的是比赛队伍的次序，第一回合：1和2 比赛，3和4 ，5 和6 ，7和8， 依次类推;

if(((j>>(i-1))^1)==(k>>(i-1))) 判断j和k是否可以比赛；

比如3支队伍，可以比赛的队伍是：

0 1    1 0    2 3     3 2  4 5  5 4  6 7  7 6   0 2  0 3   1 2  1 3  2 0  2 1  3 0  3 1  4 6  4 7  5 6   5 7  6 4  6 5  7 4   7 5  0 4   0 5   0 6   0 7  1 4   1 5  1 6   1 7  2 4  2 5
2 6  2 7  3 4  3 5  3 6  3 7  4 0  4 1  4 2  4 3  5 0  5 1  5 2  5 3  6 0  6 1  6 2  6 3  7 0  7 1    7 2   7 3

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std;
#define FF  freopen("Input.txt","r",stdin)
#define mem(x,y) memset(x,y,sizeof(x))
double dp[10][300];
double p[300][300];
int main()
{
    int n=3,i,j,k;
    while(scanf("%d",&n)&&n!=-1)
    {
        mem(dp,0);
        for(i=0;i<(1<<n);i++)
        {
            dp[0][i]=1;
            for(j=0;j<(1<<n);j++)
              scanf("%lf",&p[i][j]);
        }
        for(i=1;i<=n;i++)
          for(j=0;j<(1<<n);j++)
            for(k=0;k<(1<<n);k++)
              if(((j>>(i-1))^1)==(k>>(i-1)))
                dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k];
        double res=0;int x=-1;
        for(i=0;i<(1<<n);i++)
          if(res<dp[n][i])
          {
              res=dp[n][i];
              x=i;
          }
        printf("%d\n",x+1);
    }
    return 0;
}