poj 3071 Football 概率dp

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem(a) memset(a, 0, sizeof(a))
 4 double dp[150][150], a[150][150];
 5 int main()
 6 {
 7     int n;
 8     while(cin>>n) {
 9         if(n == -1)
10             break;
11         for(int i = 0; i<(1<<n); i++) {
12             for(int j = 0; j<(1<<n); j++) {
13                 scanf("%lf", &a[i][j]);
14             }
15         }
16         mem(dp);
17         for(int i = 0; i<(1<<n); i++)
18             dp[0][i] = 1;
19         for(int i = 1; i<=n; i++) {
20             for(int j = 0; j<(1<<n); j++) {
21                 for(int k = 0; k<(1<<n); k++) {
22                     if(((j>>(i-1))^1) == (k>>(i-1))) {
23                         dp[i][j] += dp[i-1][j]*dp[i-1][k]*a[j][k];
24                     }
25                 }
26             }
27         }
28         int ans;
29         double maxx = 0;
30         for(int i = 0; i<(1<<n); i++) {
31             if(dp[n][i]>maxx) {
32                 maxx = dp[n][i];
33                 ans = i;
34             }
35         }
36         cout<<ans+1<<endl;
37     }
38 }