首页 > 代码库 > 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)