[hdu3853]LOOPS(概率dp)

题意：迷宫是一个R*C的布局，每个格子中给出停留在原地，往右走一个，往下走一格的概率，起点在(1,1)，终点在(R,C)，每走一格消耗两点能量，求出最后所需要的能量期望。

解题关键：概率dp反向求期望，令$dp[i][j]$表示从该位置走到终点的期望能量，$a$为留在该点的位置，$b$为向下走的概率，$c$为向上走的概率，则

$dp[i][j] = a*dp[i][j] + b*dp[i + 1][j] + c*dp[i][j + 1] + 2$

移项：$dp[i][j] = (b*dp[i + 1][j] + c*dp[i][j + 1] + 2)/(1 - a)$

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<algorithm>
 7 #define eps 1e-7
 8 using namespace std;
 9 typedef long long ll;
10 double dp[1002][1002];
11 double mp[1002][1002][4];
12 int main(){
13     int n,s;
14     while(scanf("%d%d",&n,&s)!=EOF){
15         memset(dp,0,sizeof dp);
16         for(int i=1;i<=n;i++){
17             for(int j=1;j<=s;j++){
18                 for(int k=1;k<=3;k++){
19                     scanf("%lf",&mp[i][j][k]);
20                 }
21             }
22         }
23         dp[n][s]=0;
24         for(int i=n;i>0;i--){
25             for(int j=s;j>0;j--){
26                 if(i==n&&j==s) continue;
27                 if(fabs(mp[i][j][1]-1)<eps) continue;
28                 dp[i][j]=(dp[i][j+1]*mp[i][j][2]+dp[i+1][j]*mp[i][j][3]+2)/(1-mp[i][j][1]);
29             }
30         }
31         printf("%.3f
",dp[1][1]);
32     }
33 
34     return 0;
35 }

[hdu3853]LOOPS(概率dp)

相关推荐