ZOJ 3725 概率dp

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 
 7 double dp[10010][150], p[150][150];
 8 
 9 void init(int n)
10 {
11     for(int i = 0 ; i < 10010 ; i++){
12         for(int j = 0 ; j <= n ; j++){
13             dp[i][j] = 0;
14         }
15     }
16     for(int i = 1 ; i <= n ; i++){
17         dp[0][i] = 1;
18     }
19 }
20 
21 int main(){
22     int M;
23     while(~scanf("%d",&M)){
24         int n = M * (M - 1) * (M - 2) / 6;
25         for(int i = 1 ; i <= n ; i++){
26             for(int j = 1 ; j <= n ; j++){
27                 scanf("%lf",&p[i][j]);
28             }
29         }
30         init(n);
31         int Q;scanf("%d",&Q);
32         for(int i = 1 ; i <= Q ; i++){
33             int x;scanf("%d",&x);x++;//当前敌方队伍编号 
34             for(int j = 1 ; j <= n ; j++){
35                 dp[i][j] = max(dp[i][j], dp[i - 1][j] * p[j][x]);
36                 dp[i][x] = max(dp[i][x], dp[i - 1][j] * p[j][x]);
37             }
38         }
39         double res = 0;
40         for(int i = 1 ; i <= n ; i++){
41             res = max(res, dp[Q][i]);
42         }
43         printf("%.6lf\n",res);
44     }
45     
46     
47     return 0;
48 }