【HDU3853】LOOPS

题目链接：传送门
题解：
很容易想到用$dp[i][j]$表示从$(i,j)$走到$(r,c)$的期望，那么有
$dp[i][j] = p[i][j][1]\times dp[i][j] + p[i][j][2]\times dp[i][j+1] + p[i][j][3]\times dp[i+1][j] + 2$
然后整理一下得到
$dp[i][j] =\frac{p[i][j][2]\times dp[i][j+1] + p[i][j][3]\times dp[i+1][j] + 2}{1-p[i][j][1]}$
注意特判一下原地不动的概率为1的情况（此时分母为零）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int N=1005;
double f[N][N],p[N][N][3];
int r,c;int main()
{while(~scanf("%d%d",&r,&c)){for(int i=1;i<=r;i++)for(int j=1;j<=c;j++)for(int k=0;k<=2;k++)scanf("%lf",&p[i][j][k]);f[r][c]=0; for(int i=r;i;i--)for(int j=c;j;j--){if(p[i][j][0]==1||(i==r&&j==c)) continue;f[i][j]=(f[i][j+1]*p[i][j][1]+f[i+1][j]*p[i][j][2]+2)/(1-p[i][j][0]);}printf("%.3f\n",f[1][1]);}return 0;
}