【概率DP】Football

传送门:POJ3071


思路:$f_{i,j}$表示队伍i通过第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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 300
int n,ans;
double p[N][N],f[N][N];
int main(){
while (scanf("%d",&n) && n!=-1){
for (int i=0;i<1<<n;i++)
for (int j=0;j<1<<n;j++) scanf("%lf",&p[i][j]);
memset(f,0,sizeof f); for (int i=0;i<1<<n;i++) f[i][0]=1;
for (int i=1;i<=n;i++)
for (int j=0;j<1<<n;j++){
int t=(j/(1<<(i-1)))^1;
for (int k=t*(1<<(i-1));k<t*(1<<(i-1))+(1<<(i-1));k++)
f[j][i]+=f[j][i-1]*f[k][i-1]*p[j][k];
}
ans=0; for (int i=0;i<1<<n;i++) if (f[i][n]>f[ans][n]) ans=i;
printf("%d\n",ans+1);
}
return 0;
}