HDU 3853-LOOPS【期望DP】-蒲公英云

HDU 3853-LOOPS【期望DP】

小咪咪 2023-06-07 16:21 119阅读 0赞

题意：有一个R*C的迷宫，从（1,1）走到（R,C），每个格子给出停留在原地，向右走一格和向下走一格的概率，且每走一步需要2点能量，求最后所需要的能量期望。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3853

思路：f[i][j] 就表示走到(i, j) 这个点的期望能量，那么转移方程不难想到，这题主要有两个需要注意的地方，一是停留在原地的花费也是2点，二是会有停留在原地的概率为1的情况，那么此处期望只能为0，否则就会过不去。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 +10;
double f[maxn][maxn];
double x[maxn][maxn], y[maxn][maxn], z[maxn][maxn];
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i <= n + 1; ++i)
            for(int j = 0; j <= m + 1; ++j)
                f[i][j] = x[i][j] = y[i][j] = z[i][j] = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                scanf("%lf%lf%lf", &z[i][j], &x[i][j], &y[i][j]);
        f[n][m] = 0;
        for(int i = n; i >= 0; --i)
        {
            for(int j = m; j >= 0; --j)
            {
                if(i == n && j == m) continue;
                if(z[i][j] == 1) continue; //按理说数据不应该存在，算是一个坑点
                f[i][j] = (x[i][j] * f[i][j + 1] + y[i][j] * f[i + 1][j] + 2) / (1.0 - z[i][j]);
            }
        }
        printf("%.3f\n", f[1][1]);
    }
    return 0;
}