HDU 3853 向下向右找出口问题-期望dp
分类：概率dp
HDUdp
题意：初始状态在(1,1)的位置，目标是走到(n,n)，每次只能向下向右或者不移动，已知在每个格子时这三种情况的概率，每移动一步消耗2的魔力，求走到终点的使用的魔力的期望。
分析：简单的期望dp，套用之前的框架，但是这题不是+1，，而是+2，因为每次多加的那个数字是走一步的消耗，这里是2！注意p1[i][j]==1时不能计算dp[i][j]，看式子就知道了，分母不能为0。
代码：
#include<iostream>#include<cstdio>using namespace std;int n,m;double p1[1005][1005],p2[1005][1005],p3[1005][1005],dp[1005][1005];int main(){while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++) for(int j=0;j<m;j++) scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);memset(dp,0,sizeof(dp));for(int i=n-1;i>=0;i–){for(int j=m-1;j>=0;j–){if(i==n-1&&j==m-1) continue;if(p1[i][j]==1.0) continue;dp[i][j]=p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2.0;dp[i][j]/=(1.0-p1[i][j]);}}printf("%.3lf\n",dp[0][0]);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇！HDU 4311 最小曼哈顿距离-思维&卡时间-（横纵坐标分开算，排序）下一篇HDU 4312 最小切比雪夫距离-转化成曼哈顿距离再分治
顶0踩0
下午某时，天气晴，我在某地，想念你。
