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$相邻,具体可以自己推一推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}

------ 本文结束 ------