Aimee

很简单的期望dp

众所周知，期望一般倒着推，因为唯一已知的状态是$f_{r,c}$=0

定义 $f_{ij}$ 表示到达i,j之后到达终点的期望

转移方程$f{i,j}=f{i+1,j}p{i,j,2}+f{i,j+1}p{i,j,3}+f{i,j}*f_{i,j}+2$

两边都有$f_{i,j}$咋搞

移项

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
double ma[1011][1011][4];
int r,c;
double dp[1011][1011];
int main(){

    while(scanf("%d%d",&r,&c)!=EOF){
        memset(ma,0,sizeof(ma));
        memset(dp,0,sizeof(dp));
    for(int i=1;i<=r;++i){
        for(int j=1;j<=c;++j){
          scanf("%lf%lf%lf",&ma[i][j][0],&ma[i][j][1],&ma[i][j][2]);
        }
    }
    dp[r][c]=0;
    for(int j=r;j>=1;--j){
        for(int i=c;i;--i){
            if(j==r&&i==c)
            continue;
            if(ma[j][i][0]==1)
            continue;
            dp[j][i]=(ma[j][i][2]*dp[j+1][i]+ma[j][i][1]*dp[j][i+1]+2.0)/(1-ma[j][i][0]);
        }
    }+
    printf("%.3lfn",dp[1][1]);

    }
    return 0;
}