【HDU3853】LOOPS

题意

有一个R*C的方格。一个人想从（1，1）走到(r,c)。在每个格子都有三种选择，向下，向右，或者原地不动。每个格子里的每个选择都有一定的概率。而每次移动都需要消耗2点的能量，问期望消耗的能量是多少。

分析

概率DP入门题。

f[i][j]为从(i,j)到(r,c)的期望消耗。从(i,j)有三种转移方法，在原地不动，向右，向下。在原地不动的概率是G[i][j][1]，向右的概率为G[i][j][2]，向下的概率为G[i][j][3]。但是在原地不动是不消耗能量的。（想一想如果在原地不动也消耗能量的话应该怎么解决）所以转移我们只考虑转移到右边和下边的情况。

f[i][j]=(f[i+1][j]*G[i][j][2]+f[i][j+1]*G[i][j][3]+2)/(1-G[i][j][1]).

code

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <iostream>

 #include <cmath>

 using namespace std;

 const int maxn=+;

 const int eps=1e-;

 double G[maxn][maxn][];

 double f[maxn][maxn];

 int r,c;

 int main(){

     while(scanf("%d%d",&r,&c)!=EOF&&r&&c){

         for(int i=;i<=r;i++){

             for(int j=;j<=c;j++){

                 for(int l=;l<=;l++){

                     scanf("%lf",&G[i][j][l]);

                 }

             }

         }

         memset(f,,sizeof(f));

         for(int i=r;i>=;i--){

             for(int j=c;j>=;j--){

                 if(i==r&&j==c)

                     continue;

                 if(fabs(-G[i][j][])<=eps)continue;

                 f[i][j]=(f[i][j+]*G[i][j][]+f[i+][j]*G[i][j][]+)/(-G[i][j][]);

             }

         }

         printf("%.3f\n",f[][]);

     }

 return ;

 }