首页 > 代码库 > LOOPS(hdu 3853)
LOOPS(hdu 3853)
题意:迷宫是一个R*C的布局,每个格子中给出停留在原地,往右走一个,往下走一格的概率,起点在(1,1),终点在(R,C),每走一格消耗两点能量,求出最后所需要的能量期望
/* 刚开始以为这就是个**题(其实真的是),后来发现我才是**。 我设的dp[i][j]表示走到i,j的期望值,然后写个式子随便转移,后来发现这样写如果p[i][j][1]为1的话,这样转移就GG了。 然后发现题解们设得dp[i][j]表示i,j走到n,m的期望,然后倒着转移,这样就避免了上述情况。 */ #include<cstdio> #include<iostream> #include<cstring> #define N 1010 using namespace std; double p[N][N][4],dp[N][N];int n,m; void work(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lf%lf%lf",&p[i][j][1],&p[i][j][2],&p[i][j][3]); dp[n][m]=0; for(int i=n;i;i--) for(int j=m;j;j--){ if((i==n&&j==m)||p[i][j][1]==1) continue; dp[i][j]=(dp[i][j+1]*p[i][j][2]+dp[i+1][j]*p[i][j][3]+2)/(1-p[i][j][1]); } printf("%.3lf\n",dp[1][1]); } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ memset(dp,0,sizeof(dp)); memset(p,0,sizeof(p)); work(); } return 0; }
LOOPS(hdu 3853)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。