hdu 3853 LOOPS（基础DP求期望）
题目大意
有一个人被困在一个 R*C(2<=R,C<=1000) 的迷宫中，起初他在 (1,1) 这个点，迷宫的出口是 (R,C)。在迷宫的每一个格子中，他能花费 2 个魔法值开启传送通道。假设他在 (x,y) 这个格子中，开启传送通道之后，有 p_lift[i][j] 的概率被送到 (x,y+1)，有 p_down[i][j] 的概率被送到 (x+1,y)，有 p_loop[i][j] 的概率被送到 (x,y)。问他到出口需要花费的魔法值的期望是多少。
做法分析
令：f[i][j] 表示从 (i,j) 这个点到下一点花费的魔法值的期望。
那么，我们有：
f[i][j] = 2+p_loop[i][j]*f[i][j] + p_left[i][j]*f[i][j+1] + p_down[i][j]*f[i+1][j]
移项可得：
(1-p_loop[i][j])*f[i][j] = 2+p_left[i][j](f[i][j+1] + p_down[i][j]*f[i+1][j]
#include<stdio.h> #include<math.h> #include<string.h> double p[3][1005][1005]; double f[1005][1005]; bool vs[1005][1005]; int R,C; double DP(int x,int y) { if(x==R&&y==C)return 0; if(x>R||y>C)return 0; if(vs[x][y])return f[x][y]; if(fabs(p[0][x][y]-1)<1e-6) { vs[x][y]=1; return f[x][y]=0; } vs[x][y]=1; return f[x][y]=(2+p[1][x][y]*DP(x,y+1)+p[2][x][y]*DP(x+1,y))/(1-p[0][x][y]); } int main() { while(scanf("%d%d",&R,&C)!=EOF) { for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) scanf("%lf%lf%lf",&p[0][i][j],&p[1][i][j],&p[2][i][j]); memset(f,0,sizeof(f)); memset(vs,0,sizeof(vs)); printf("%.3lf ",DP(1,1)); } }