首页 > 代码库 > hdu 3853 LOOPS (概率dp)
hdu 3853 LOOPS (概率dp)
/* dp[i][j]表示(i,j)到(R,C)需要消耗的能量 则: dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2;///+2 转移到下一个能量要消耗2 化简得: dp[i][j]=((p2[i][j]*dp[i][j+1])+(p3[i][j]*dp[i+1][j])+2)/(1-p1[i][j]); */ # include <stdio.h> # include <algorithm> # include <string.h> # include <iostream> using namespace std; double dp[1010][1010],p1[1010][1010],p2[1010][1010],p3[1010][1010]; int main() { int r,c,i,j; while(~scanf("%d%d",&r,&c)) { for(i=1;i<=r;i++) { for(j=1;j<=c;j++) scanf("%lf %lf %lf",&p1[i][j],&p2[i][j],&p3[i][j]); } dp[r][c]=0; for(i=r;i>=1;i--) { for(j=c;j>=1;j--) { if(i==r&&j==c) continue; if(p1[i][j]==1) continue; dp[i][j]=((p2[i][j]*dp[i][j+1])+(p3[i][j]*dp[i+1][j])+2)/(1-p1[i][j]); } } printf("%.3lf\n",dp[1][1]); } return 0; }
hdu 3853 LOOPS (概率dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。