HDU 3853-LOOPS【期望DP】

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

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

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=3853][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;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_3853]: http://acm.hdu.edu.cn/showproblem.php?pid=3853

发表评论取消回复

表情：

评论列表（有 0 条评论，3人围观）

还没有评论，来说两句吧...

相关阅读

相关期望DP入门

期望DP一般步骤： 1.模拟过程，找出线性性质，作为阶段（这本质上也是线性DP） 2.涉及DP状态原则：体现线性性质体现边权根据对期望有无贡献来设计状态

雨点打透心脏的1/2处/ 2024年03月17日 17:05/ 0 赞/ 39 阅读

相关概率期望dp

简易的入门：http://kicd.blog.163.com/blog/static/126961911200910168335852/ 大神的总结：http://blog

港控/mmm°/ 2023年08月17日 16:25/ 0 赞/ 99 阅读

相关 HDU 3853-LOOPS【期望DP】

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

小咪咪/ 2023年06月07日 16:21/ 0 赞/ 4 阅读

相关 POJ - 2096 Collecting Bugs【期望DP】

题意：某个系统中有n个子系统和m个bug类型，该系统每天会出现一个bug （属于某个子系统和某个bug类型），bug的类型是等概率的，bug也是等概率地出现在每个子系统的。问所

àì夳堔傛蜴生んèń/ 2023年06月02日 13:54/ 0 赞/ 16 阅读

相关【期望DP】[poj2096]Collecting Bugs

偷一波翻译： > 工程师可以花费一天去找出一个漏洞——这个漏洞可以是以前出现过的种类，也可能是未曾出现过的种类，同时，这个漏洞出现在每个系统的概率相同。要求得出找到n种漏洞，

妖狐艹你老母/ 2023年06月01日 06:08/ 0 赞/ 8 阅读

相关 HDU 3853 LOOPS （概率DP）

HDU 3853 LOOPS （概率DP）[http://acm.hdu.edu.cn/showproblem.php?pid=3853][http_acm.hdu.edu.c

刺骨的言语ヽ痛彻心扉/ 2022年08月22日 00:03/ 0 赞/ 143 阅读

相关 hdu 3853 概率dp入门

题意：在一块r\c的棋盘上，从位置(1,1)的地方走到位置为(r,c)的地方，每走一步的代价为2，在位置(i,j)可能会走到位置(i+1,j),(i,j+1)以及(i,j)

落日映苍穹つ/ 2022年08月20日 15:18/ 0 赞/ 167 阅读

相关 hdu 5119 dp

Happy Matt Friends Time Limit: 6000/6000 MS (Java/Others) Memory Limit: 510000/510

忘是亡心i/ 2022年08月08日 14:52/ 0 赞/ 200 阅读

相关 HDU 4418 （期望dp 高斯消元）

题意：有一个坐标轴，从s点开始，为了到达e点，走的时候是周而复始循环的，比如 0 1 2 3 3 2 0.。。，从一个点开始，每走k步都有pk的概率停下，问正好停在目标点的期

以你之姓@/ 2022年05月15日 05:28/ 0 赞/ 181 阅读

相关 uva-10828 期望dp+gauss

[传送门][Link 1] 题意：给你一个有向图，从1号节点出发，问经过某个点的期望次数。思路：传递闭包写错wa到哭。设 dp\[i\]为经过i点期望 dp\[v\]=

浅浅的花香味﹌/ 2022年05月09日 11:08/ 0 赞/ 164 阅读