poj 3071 Football

#include <iostream>#include <stdio.h>#include <algorithm>#include <string.h>#include <vector>#define cls(p) memset(p,0,sizeof(p))using namespace std;const int MAX=3e2;double dp[10][MAX];double ks[MAX][MAX];int N,M;void init(){cls(ks);cls(dp);for(int i=0;i<M+3;i++)dp[0][i]=1;}char s[MAX];int main(){    while(~scanf("%d",&N)){if(N==-1) break;M=1<<N;init();        for(int i=0;i<M;i++)for(int j=0;j<M;j++)     scanf("%lf",&ks[i][j]);        int left,right,mid,L=1;for(int i=1;i<=N;i++){ for(left=0;left<M;left+=2*L){mid=left+L;right=mid+L;     for(int k1=left;k1<mid;k1++)for(int k2=mid;k2<right;k2++){  dp[i][k1]+=dp[i-1][k1]*dp[i-1][k2]*ks[k1][k2];  dp[i][k2]+=dp[i-1][k1]*dp[i-1][k2]*ks[k2][k1];}}L*=2;}int t;     double ans=0;     for(int i=0;i<M;i++) if(ans<dp[N][i]){ans=dp[N][i];t=i;}printf("%dn",t+1);}    return 0;}