HDU 4405-Aeroplane chess【期望DP】

爱被打了一巴掌 2023-06-07 12:28 58阅读 0赞

题意：0到n的格子，每次仍色子走1到6步，也可能会有飞行棋，直接跳到某格，问你走到n的期望步数。

思路：期望倒着推，f\[i\] 就表示走到i格子的期望。正着考虑的话你不知道当前位置是哪个地方来的，可能是之前六个位置的，也可能是之前某个飞行棋跳过来的，所以我们倒着考虑，每个位置只会去往六个地方。所以f\[i\] = sum( f\[i + k\] / 6 ) + 1 ,  1 <= k <= 6

然后对于飞行棋的格子来说，假设x要跳到y，那么f\[x\] = f\[y\] ， 边界f\[n\] = 0, 目标状态f\[0\]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5 +10;
    double f[maxn];
    int vis[maxn];
    
    int main()
    {
        int n, m;
        while(~scanf("%d%d", &n, &m) && n + m)
        {
            for(int i = 0; i <= n + 2; ++i) f[i] = 0, vis[i] = -1;
            for(int i = 1; i <= m; ++i)
            {
                int x, y;
                scanf("%d%d", &x, &y);
                vis[x] = y;
            }
            f[n] = 0;
            for(int i = n - 1; i >= 0; --i)
            {
                if(vis[i] != -1) //如果这一步跳棋
                    f[i] = f[vis[i]];
                else //否则就考虑往后面6步内的情况
                {
                    for(int j = 1; j <= 6; ++j)
                        if(j + i <= n)
                            f[i] += f[i + j] / 6.0;
                    f[i] += 1;
                }
            }
            printf("%.4f\n", f[0]);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关期望DP入门

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

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

相关概率期望dp

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

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

相关 HDU 3853-LOOPS【期望DP】

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

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

相关 HDU 4405-Aeroplane chess【期望DP】

题意：0到n的格子，每次仍色子走1到6步，也可能会有飞行棋，直接跳到某格，问你走到n的期望步数。思路：期望倒着推，f\[i\] 就表示走到i格子的期望。正着考虑的话你不知道

爱被打了一巴掌/ 2023年06月07日 12:28/ 0 赞/ 59 阅读

相关【期望DP】[UVA1498] Activation

显然是概率DP 我们用dp\[i\]\[j\]表示队伍中有i个人，lyk的小迷妹现在排在j这个位置时的概率大小不难列出下列转移方程：（显然已经排到前面k个位置的时候是

太过爱你忘了你带给我的痛/ 2023年06月01日 06:09/ 0 赞/ 114 阅读

相关 HDU 5794 A Simple Chess（数论）

There is a n×m board, a chess want to go to the position (n,m) from the position (1,1)

Love The Way You Lie/ 2022年09月25日 02:30/ 0 赞/ 265 阅读

相关 HDU 5245 Joyful (概率期望)

HDU 5245 Joyful (概率) ：[http://acm.hdu.edu.cn/showproblem.php?pid=5245][http_acm.hdu.edu.

系统管理员/ 2022年08月21日 14:41/ 0 赞/ 116 阅读

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

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

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

相关 uva-10828 期望dp+gauss

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

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

相关 LightOJ 1030 Discovering Gold + Hdu4405 Aeroplane chess (期望)

相似的两题一起总结。 LightOJ 1030 Discovering Gold 题目链接：http://lightoj.com/volume\_showproble

妖狐艹你老母/ 2021年11月04日 10:28/ 0 赞/ 330 阅读