poj 3071 Football

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<map>

#include<cmath>

#define LL long long



using namespace std;



const int N=130;



double win[N][N];//                

double beat[N][N];// i j   

double pro(int k,int x,int l,int r)// k   x    l r      

{

    if(win[k][x]>=0.0)

    return win[k][x];//   

    if(x==0)

    {

        win[k][x]=1.0;// 0         

        return win[k][x];

    }

    int mid=(l+r)>>1;

    double ftemp=0.0;

    if(k<=mid)//  k              

    {

        for(int i=mid+1;i<=r;++i)

        {

            ftemp+=(beat[k][i]*pro(i,x-1,mid+1,r));//                   

        }

        win[k][x]=pro(k,x-1,l,mid)*ftemp;//           

    }else

    {

        for(int i=l;i<=mid;++i)

        {

            ftemp+=(beat[k][i]*pro(i,x-1,l,mid));

        }

        win[k][x]=pro(k,x-1,mid+1,r)*ftemp;

    }

    return win[k][x];

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        if(n==-1)

        break;

        int m=int(pow(2,n));

        for(int i=1;i<=m;++i)

        {

            for(int j=1;j<=m;++j)

            {

                scanf("%lf",&beat[i][j]);

            }

        }

        for(int i=1;i<=m;++i)

        {

            for(int j=0;j<=n;++j)

            {

                win[i][j]=-1.0;//   

            }

        }

        int ans=1;

        for(int i=1;i<=m;++i)

        {

            if(pro(i,n,1,m)>win[ans][n])//                 

            ans=i;

        }

        printf("%d
",ans);

    }

    return 0;

}