?
大致题意：有2^n个足球队分成n组打比赛。给出一个矩阵a[][],a[i][j]表示i队赢得j队的概率。n次比赛的流程像这样France '98。 问最后哪个队最可能得冠军。
思路：概率dp问题。ans[i][j]表示第i轮中j队获胜的概率。
#include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-8 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 10; int n; int m; double a[130][130]; double ans[maxn][130]; int pow2[8] = {1,2,4,8,16,32,64,128}; void solve() { memset(ans,0,sizeof(ans)); int t,r; for(int i = 1; i <= m; i++) { if(i&1) ans[1][i] = a[i][i+1]; else ans[1][i] = a[i][i-1]; } for(int i = 2; i <= n; i++) { for(int j = 1; j <= m; j++) { r = pow2[i]; //周期 if(j % r == 0) t = j/r; else t = j/r+1; if(j%r >= 1 && j%r <= r/2) { for(int k = t*r; ; k--) { if(k%r != 0 && k%r <= r/2) break; ans[i][j] += ans[i-1][j]*a[j][k]*ans[i-1][k]; } } else { for(int k = (t-1)*r+1; ; k++) { if(k%r >= r/2+1) break; ans[i][j] += ans[i-1][j]*a[j][k]*ans[i-1][k]; } } } } } int main() { while(~scanf(%d,&n)) { if(n == -1) break; m = pow2[n]; for(int i = 1; i <= m; i++) for(int j = 1; j <= m; j++) scanf(%lf,&a[i][j]); solve(); double res = ans[n][1]; int pos = 1; for(int i = 2; i <= m; i++) { if(res < ans[n][i]) { res = ans[n][i]; pos = i; } } printf(%d ,pos); } return 0; }