Hdu 3853(概率期望DP)

hdu 3853
设$dp(i,j)$为$(i,j)$到$(r,c)$的步数期望,那么可以列出下列状态转移方程:
$$dp(i,j)=\frac{dp(i,j+1) \times P_2 + dp(i+1,j) \times P_3}{1-P_1}$$
但是当$P_1=1$时,$dp(i,j)=0$,因为这个点肯定无法到达终点,设为$0$表示该点不影响其他点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5, P1 = 0, P2 = 1, P3 = 2;
const db eps = 1e-9;
db p[MAXN][MAXN][3], dp[MAXN][MAXN];
int r, c;
void clean() {
ms(dp, 0);
}
void solve() {
clean();
for (int i=1;i<=r;i++) {
for (int j=1;j<=c;j++) {
scanf("%lf%lf%lf", &p[i][j][P1], &p[i][j][P2], &p[i][j][P3]);
}
}
for (int i=r;i>=1;i--) {
for (int j=c;j>=1;j--) {
if (fabs(1.0-p[i][j][P1])<eps) continue;
dp[i][j] = (db)(dp[i][j+1]*p[i][j][P2]+dp[i+1][j]*p[i][j][P3]+2)/(db)(1.0-p[i][j][P1]);
}
}
printf("%.3f\n", dp[1][1]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &r, &c)==2) solve();
return 0;
}

------ 本文结束 ------