首页 > 代码库 > (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的,但却有着三维的外衣
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。