HDU3853

期望DP

N*M的网格

每个格子有三个概率，分别为传送到自己，下方，右侧的格子的概率，每一次传送的费用为2.

求从左上角的（1,1）到右下角的（n,m）的期望费用

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
int n,m;
double gl0[maxn][maxn],gl1[maxn][maxn],gl2[maxn][maxn],f[maxn][maxn];

int main()
{
    while(scanf("%d%d",&n,&m)==2){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%lf%lf%lf",&gl0[i][j],&gl1[i][j],&gl2[i][j]);
    f[n][m]=0;
    for(int i=n;i>0;--i)
        for(int j=m;j>0;--j)
        {
            if(gl0[i][j]==1||i==n&&j==m)continue;
            f[i][j]=(f[i+1][j]*gl2[i][j]+f[i][j+1]*gl1[i][j]+2)/(1-gl0[i][j]);
        }
    printf("%.3lf
",f[1][1]);
    }
    return 0;
}