题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3853

题意：在一个n*m的网格中，你有一定的概率待在原地，向右走一格，向下走一格。每次操作都会消耗2个魔法，问从（1,1）走到（n,m）所需的魔法期望是多少。

思路：设dp[i][j]表示从(i,j)走到(n,m)还需要的魔法数。先找到期待值dp[n][m]=0，然后有（1-a[i][j].x）的概率是可以不待在原地的，再根据概率之间的一些转换可以得出：

dp[i][j]=(a[i][j].y*dp[i][j+1]+a[i][j].z*dp[i+1][j]+2)/(1-a[i][j].x);

#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
double dp[1010][1010];
struct node
{
    double x,y,z;
}a[1010][1010];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lf%lf%lf",&a[i][j].x,&a[i][j].y,&a[i][j].z);
        dp[n][m]=0;
        for(int i=n;i>=1;i--)
            for(int j=m;j>=1;j--)
        {
            if(i==n&&j==m)
                continue;
            if(a[i][j].x==1)
                continue;
            dp[i][j]=(a[i][j].y*dp[i][j+1]+a[i][j].z*dp[i+1][j]+2)/(1-a[i][j].x);
        }
        printf("%.3lf\n",dp[1][1]);
    }
}