poj 3071(概率DP)

poj 3071
题意：有$2^n​$个队进行$n​$轮比赛，每轮比赛相邻(例如1-2, 3-4, 5-6)的两个队比赛一场，给出胜率矩阵，求出哪个队最大几率获胜。
设$dp(i,j)$为第$i$轮比赛$j$赢的概率。
$dp(i,j)=\sum dp(i-1, j) \times dp(i-1, k) \times p(j, k)$ (全概率公式)
其中$k$是和$j$相邻的队。
通过分析队编号的二进制(从0开始),可以发现(j>>(i-1))^1)==(k>>(i-1)的时候$k$和$j$相邻，具体可以自己推一推。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 10, MAXNF = 200;
int n, len;
db p[MAXNF][MAXNF], dp[MAXN][MAXNF];
void clean() {
    ms(dp, 0);
}
void solve() {
    clean();
    len = (1<<n);
    for (int i=0;i<len;i++) for (int j=0;j<len;j++) scanf("%lf", &p[i][j]);
    for (int i=0;i<len;i++) dp[0][i] = 1.0;
    for (int i=1;i<=n;i++) {
        for (int j=0;j<len;j++) {
            for (int k=0;k<len;k++) {
                if (((j>>(i-1))^1)==(k>>(i-1))) {
                    dp[i][j] += dp[i-1][j] * dp[i-1][k] * p[j][k];
                }
            }
        }
    }
    db ans = 0.0; int k = 0;
    for (int i=0;i<len;i++) {
        if (dp[n][i]>ans) ans = dp[n][i], k = i;
    }
    printf("%d\n", k+1);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d", &n)==1&&n!=-1) solve();
    return 0;
}