首页 > 代码库 > (review)zoj4800 二维dp 状态转移很灵活

(review)zoj4800 二维dp 状态转移很灵活

 1 #include<iostream>
 2 #include<stdio.h>
 3 
 4 using namespace std;
 5 
 6 double dp[10005][125];
 7 double p[125][125];
 8 int pk[10005];
 9 
10 int N,M;
11 
12 double fmax(double a,double b){
13     if(a-b>0) return a;else return b;
14 }
15 int main(){
16     //freopen("out.txt","w",stdout);
17     while(~scanf("%d",&M)){
18         M=(M)*(M-1)*(M-2)/6;
19         for(int i=0;i<M;i++){
20             for(int j=0;j<M;j++) scanf("%lf",&p[i][j]);
21         }
22         scanf("%d",&N);
23         for(int i=1;i<=N;i++) scanf("%d",&pk[i]);
24 
25         for(int i=0;i<M;i++) dp[1][i]=p[i][pk[1]];
26         for(int i=0;i<M;i++){
27             for(int j=2;j<=N;j++) dp[j][i]=0.0;
28         }
29         for(int i=2;i<=N;i++){
30             for(int j=0;j<M;j++){
31                 if (j==pk[i-1]){
32                     for(int k=0;k<M;k++){
33                         dp[i][j]=fmax(dp[i][j],dp[i-1][k]*p[j][pk[i]]);
34                     }
35                 }else {
36                     dp[i][j]=dp[i-1][j]*p[j][pk[i]];
37                 }
38             }
39         }
40 
41         double ans=-1.0;
42         for(int i=0;i<M;i++) ans=fmax(ans,dp[N][i]);
43 
44         printf("%lf\n",ans);
45 
46     }
47     return 0;
48 }

题解:dp[i][j]:表示用j号队员打败了第i个对手的最大的概率。

昨天晚上一直W。

dp很容易写错,下面是我的经验:

1、尽量要考虑第一层的边界(多是多个入口的题目要这样)

2、下标一定要搞对

3、dp定义数组一定不能过小,不然会越界出错

4、初始化注意下标范围

 

出错时检查:

11、输入输出1、下标定义2、初始化的下标3、小数据4、状态方程的逻辑性是否正确

 

我觉得这道题的巧妙在于,分析复杂度后你会发现是N*M的,但却有着三维的外衣