题目大意
有一场足球赛，一共有(n)轮，上一轮胜出的队伍与这一轮与其相邻的队伍比赛(1和2，3和4) 给你任意两个队比赛会获胜的概率，求最后那个队获胜的概率最大。
解题思路
第一轮两个队之间有一个会获胜，第二轮四个队之间有一个会获胜，第三轮8个队之间有一个会获胜...第一轮分成人数为1的小组，第二轮分成人数为2的小组，第三轮分成人数为3的小组...发现每轮比赛都是第1组和第2组打，第3组和第4组打。
然后就是计算概率了，可以发现每轮每个队的获胜概率有递推关系，设(dp[i][j])表示第(i)队第(j)轮胜出，那么第(i)队第(j+1)轮胜出的概率就是和相邻组打所有胜出情况的概率之和。即(dp[i][j+1] = sum {dp[i][j] imes p[i][k] imes dp[k][j]}).
const int maxn = 1e3+10;
const int maxm = 1e6+10;
double p[maxn][maxn], dp[maxn][maxn];
int main() {
//IOS;
int t;
while(cin >> t && (~t)) {
int n = 1<<t;
for (int i = 0; i<n; ++i)
for (int j = 0; j<n; ++j)
scanf("%lf", &p[i][j]);
for (int i = 0; i<n; ++i) dp[i][0] = 1;
for (int i = 0; i<t; ++i) {
int sz = 1<<i;
//cout << "_____________i_______________" << endl;
for (int j = 0; j<n; ++j) {
//cout << "-----j-----" << endl;
int now = j/sz;
double sum = 0;
if (now&1) {
for (int k = (now-1)*sz; k<now*sz; ++k) {
sum += dp[j][i]*p[j][k]*dp[k][i];
//cout << j << ' ' << k << endl;
}
}
else {
for (int k = (now+1)*sz; k<(now+2)*sz; ++k) {
sum += dp[j][i]*p[j][k]*dp[k][i];
//cout << j << ' ' << k << endl;
}
}
dp[j][i+1] = sum;
//cout << sum << endl;
}
}
int ans = 0;
for (int i = 0; i<n; ++i)
if (dp[ans][t]<dp[i][t]) ans = i;
cout << ans+1 << endl;
}
return 0;
}