hdu 3853 概率dp入门

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

题意：

在一块r\*c的棋盘上，从位置(1,1)的地方走到位置为(r,c)的地方，每走一步的代价为2，在位置(i,j)可能会走到位置(i+1,j),(i,j+1)以及(i,j)，题目中给出每个点走向下一个方向的概率，求花的总代价。

分析：

一道很基础的概率dp，dp\[i\]\[j\]表示的是从位置(i,j)走到(r,c)所花的代价，那么dp\[r\]\[c\] = 0 , 最后要求的就是dp\[1\]\[1\]。

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <algorithm>
    #include <queue>
    #include <stack>
    #include <map>
    
    using namespace std ;
    #define mem(a) memset(a,0,sizeof(a))
    #define inf 100000005
    
    int const maxn = 1005;
    double dp[maxn][maxn];
    //dp[i][j]表示的是从位置(i,j)走到位置(n,c)需要的代价,答案是dp[1][1]
    
    struct node
    {
        double now;
        double y_1;
        double x_1;
    }A[maxn][maxn];
    
    int main()
    {
        int r,c;
        while(scanf("%d%d",&r,&c)!=EOF)
        {
            for(int i = 1 ; i <= r ; i++)
            {
                for(int j = 1 ; j <= c ; j++)
                {
                    scanf("%lf%lf%lf",&A[i][j].now,&A[i][j].y_1,&A[i][j].x_1);
                }
            }
            mem(dp);
            dp[r][c] = 0 ;
            for(int i = r ; i > 0 ; i--)
            {
                for(int j = c ; j > 0 ; j--)
                {
                    if(i==r&&j==c)continue;
                    if(A[i][j].now==1)continue;   //这里就是这个题目的陷阱，因为假如在一个点在原地踏步的概率是1的话，那么
                    //走进来就出不去了
                    dp[i][j] = (dp[i+1][j]*A[i][j].x_1 + dp[i][j+1]*A[i][j].y_1 + 2)/(1-A[i][j].now) ;
                }
            }
            printf("%.3lf\n",dp[1][1]);
        }
        return 0 ;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 3853-LOOPS【期望DP】

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

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

相关烟花（概率dp）

https://ac.nowcoder.com/acm/problem/18200 分析： double x = 1.0000 - arr\[i\]; doubl

秒速五厘米/ 2023年01月13日 15:56/ 0 赞/ 205 阅读

相关 HDU 5159 Card （概率DP）

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

ゝ一纸荒年。/ 2022年08月22日 00:03/ 0 赞/ 187 阅读

相关 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 赞/ 144 阅读

相关 HDU Walk （概率DP）

HDU Walk （概率DP）：[http://acm.hdu.edu.cn/showproblem.php?pid=5001][http_acm.hdu.edu.cn_sho

柔光的暖阳◎/ 2022年08月21日 11:58/ 0 赞/ 184 阅读

相关 hdu 4586 概率dp

题意：扔一个有n面的骰子，可能得到正面朝上的那个面上面的数字，有一些面比较特殊，扔到这些面上之后可能继续扔，问最终能等到的数字和的期望。分析：这道题

灰太狼/ 2022年08月20日 15:21/ 0 赞/ 170 阅读

相关 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 赞/ 168 阅读

相关 poj2096 概率dp入门

题意：一个系统有s个子系统，一共会产生n中bug。某人一天可以发现一个bug，这个bug属于一个子系统，属于一个种类，每个bug属于某个子系统的概率是1/s,属于某个分类的

我就是我/ 2022年08月20日 15:16/ 0 赞/ 177 阅读

相关 HDU 5955 gauss概率dp+ac自动机

题意：有n个人，每个人猜一个\[1,6\]长度为L的序列，然后无限制的掷骰子，先掷到的那个序列，那个人就是winner，问每个人赢得概率。思路：骰子是掷无限次的，但是有

川长思鸟来/ 2022年05月08日 10:52/ 0 赞/ 197 阅读

相关 hdu 6558 The Moon（概率dp）

题意：每赢一局 (赢的概率为 p) 能以概率 q 开一个箱子，如果开箱失败 q = q + 2%，如果该局失败 q = q + 1.5%。求直到成功开箱之前期望。分析

ゝ一世哀愁。/ 2021年11月16日 15:24/ 0 赞/ 285 阅读