【概率DP】Football

动态规划DP

传送门：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;
}