poj 3071 Football

http://poj.org/problem?id=3071
概率dp，dp[i][j]表示第i次比赛，第j支队伍胜出的概率。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1000
 5 using namespace std;
 6 
 7 double dp[maxn][maxn];
 8 double a[maxn][maxn];
 9 
10 int main()
11 {
12     int n;
13     while(scanf("%d",&n)!=EOF)
14     {
15         if(n==-1) break;
16         memset(dp,0,sizeof(dp));
17         memset(a,0,sizeof(a));
18         for(int i=0; i<(1<<n); i++)
19         {
20             for(int j=0; j<(1<<n); j++)
21             {
22                 scanf("%lf",&a[i][j]);
23             }
24         }
25         for(int i=0; i<(1<<n); i++) dp[0][i]=1;
26         for(int i=1; i<=n; i++)
27         {
28             for(int j=0; j<(1<<n); j++)
29             {
30                 for(int k=0; k<(1<<n); k++)
31                 {
32                     if(((j>>(i-1))^1)==((k>>(i-1))))
33                     {
34                         dp[i][j]+=dp[i-1][j]*dp[i-1][k]*a[j][k];
35                     }
36                 }
37             }
38         }
39         int t1=0;
40         for(int i=0; i<(1<<n); i++)
41         {
42             if(dp[n][i]>dp[n][t1])
43             {
44                 t1=i;
45             }
46         }
47         printf("%d
",t1+1);
48     }
49     return 0;
50 }
View Code