首页 > 代码库 > hdu3853（概率dp）
hdu3853（概率dp）
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=3853
题意：有一个人被困在一个 R*C(2<=R,C<=1000) 的迷宫中，起初他在 (1,1) 这个点，迷宫的出口是 (R,C)。在迷宫的每一个格子中，他能花费 2 个魔法值开启传送通道。假设他在 (x,y) 这个格子中，开启传送通道之后，有 p_lift[i][j] 的概率被送到 (x,y+1)，有 p_down[i][j] 的概率被送到 (x+1,y)，有 p_loop[i][j] 的概率被送到 (x,y)。问他到出口需要花费的魔法值的期望是多少。
分析：dp[i][j]表示从（i，j）到终点（n，m）花费的魔法值的期望。
则有：dp[i][j]=(2+dp[i][j])*p[i][j][0]+(2+dp[i][j+1])*p[i][j][1]+(2+dp[i+1][j])*p[i][j][2];
移项：dp[i][j]=(dp[i][j+1]*p[i][j][1]+dp[i+1][j]*p[i][j][2]+2*((p[i][j][0]+p[i][j][1]+p[i][j][2])==1))/(1-p[i][j][0]);
#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-6#define N 1000010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;double dp[1010][1010];double p[1010][1010][3];int main(){ int n,m; while(scanf("%d%d",&n,&m)>0) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<=2;k++) scanf("%lf",&p[i][j][k]); for(int i=n;i>=1;i--) for(int j=m;j>=1;j--) { if(n==i&&j==m) { dp[i][j]=0; continue; } if(fabs(1-p[i][j][0])<eps)//不断在原地循环 { dp[i][j]=inf; continue; } dp[i][j]=(2+dp[i][j+1]*p[i][j][1]+dp[i+1][j]*p[i][j][2])/(1-p[i][j][0]); } printf("%.3lf\n",dp[1][1]); }}
hdu3853（概率dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。