HDU-4405-Aeroplane chess

ACM模版

描述

题解

概率 DPDP,求期望。

状态转移方程很容易想,设 dp[i]dp[i] 表示在位置 ii 还需要多少期望才能到达终点,那么 dp[n]=0dp[n] = 0,求 dp[0]dp[0] 即可。

状态转移方程如下:

dp[i]=∑x=16dp[i+x]6.0+1

dp[i] = \sum_{x = 1}^6 \frac{dp[i + x]}{6.0} + 1

但是题目中提到了传送门,也就是说当到达 aa 时直接飞到 b (a<b)b\ (a < b),那么这种情况要对 dp[]dp[] 进行特判,使 dp[a]=dp[b]dp[a] = dp[b]。

剩下的就没有什么问题了,具体看代码吧!

代码

#include <cstdio>
#include <algorithm>
#include <cstring>

#define ll long long

const int MAXN = 1e5 + 10;

int n, m;
int vis[MAXN];
double dp[MAXN];

int main()
{
    while (~scanf("%d%d", &n, &m) && n + m)
    {
        memset(dp, 0, sizeof(dp));
        memset(vis, -1, sizeof(vis));

        int a, b;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &a, &b);
            vis[a] = b;
        }

        for (int i = n - 1; i >= 0; i--)
        {
            if (vis[i] == -1)
            {
                for (int j = 1; j <= 6; j++)
                {
                    dp[i] += dp[i + j] / 6.0;
                }
                dp[i] += 1;
            }
            else
            {
                dp[i] = dp[vis[i]];
            }
        }

        printf("%.4lf\n", dp[0]);
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木子昭的博客

Tensorflow可视化编程安装Tensoflow1.0将加法运算以图形化方式展示实现简单的线性回归为程序添加作用域模型的保存与恢复(保存会话资源)

安装Tensoflow1.0 Linux/ubuntu: python2.7: pip install https://storage.googleapis.c...

3478
来自专栏一个爱瞎折腾的程序猿

通过脚本下载GO被墙或常用的相关包

941
来自专栏ATYUN订阅号

【教程】利用Tensorflow目标检测API确定图像中目标的位置

深度学习提供了另一种解决“Wally在哪儿”(美国漫画)问题的方法。与传统的图像处理计算机视觉方法不同的是,它只使用了少量的标记出Wally位置的示例。 在我的...

7026
来自专栏人工智能LeadAI

YOLO:实时目标检测

一瞥(You Only Look Once, YOLO),是检测Pascal VOC(http://host.robots.ox.ac.uk:8080/pasc...

9997
来自专栏AI研习社

Github 项目推荐 | TensorFlow 概率推理工具集 —— probability

Probability 是 TensorFlow 的概率推理工具集,它是集建模工具、推理算法、一些有用的模型和一般统计计算于一身的开发工具集合。利用 Tenso...

5554
来自专栏Jack-Cui

Caffe学习笔记(一):CIFRA-10在Caffe上进行训练学习

运行平台:Ubuntu14.04     安装完Caffe后,如何开始学习Caffe呢?一个不错的方法就是从Caffe自带的examples开始学起。在caff...

3137
来自专栏计算机视觉与深度学习基础

【深度学习】使用tensorflow实现AlexNet

AlexNet是2012年ImageNet比赛的冠军,虽然过去了很长时间,但是作为深度学习中的经典模型,AlexNet不但有助于我们理解其中所使用的很多技巧,...

44910
来自专栏数据处理

笔记一python代码

1693
来自专栏CNN

MobileNet V1官方预训练模型的使用

MobileNet V1的网络结构可以直接从官方Github库中下载定义网络结构的文件,地址为:https://raw.githubusercontent.co...

6992
来自专栏mathor

“达观杯”文本智能处理挑战赛

 由于提供的数据集较大,一般运行时间再10到15分钟之间,基础电脑配置在4核8G的样子(越消耗内存在6.2G),因此,一般可能会遇到内存溢出的错误

3592

扫码关注云+社区

领取腾讯云代金券