用记忆化写概率DP写的越来越纯真了。。

感觉记忆化很好写。。。

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
#define maxn 1100
#define eps 1e-6
#define zero(x) (fabs(x)<0?0:x)
double mp[maxn][maxn][4];
double dp[maxn][maxn];
int n,m;
double dos(int x,int y)
{
    if(x>n||y>m)return -2;
    if(dp[x][y]>-0.5)return dp[x][y];
    double a,b,c;
    a=mp[x][y][1];
    if(zero(a-1)==0)return 0;
    b=mp[x][y][2];
    c=mp[x][y][3];
    dp[x][y]=2.0*a;
    dp[x][y]+=b*(dos(x,y+1)+2);
    dp[x][y]+=c*(dos(x+1,y)+2);
    dp[x][y]=dp[x][y]/(1-a);
    return dp[x][y];
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,-1,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                for(int k=1;k<=3;k++)
                {
                    scanf("%lf",&mp[i][j][k]);
                }
            }
        }
        dp[n][m]=0;
        printf("%.3f\n",dos(1,1));
    }
    return 0;
}