P5155 [USACO18DEC]Balance Beam

    • 179通过
    • 728提交
  • 题目提供者 StudyingFather
  • 评测方式 云端评测
  • 标签 USACO 2018
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Bessie为了存钱给她的牛棚新建一间隔间,开始在当地的马戏团里表演,通过在平衡木上小心地来回走动来展示她卓越的平衡能力。

    Bessie能够通过表演赚到的钱取决于她最终成功跳下平衡木的位置。平衡木上从左向右的位置记为 $ 0,1,\ldots,N+1 $ 。如果Bessie到达了位置 $ 0 $ 或是 $ N+1 $ ,她就会从平衡木的一端掉下去,遗憾地得不到报酬。

    如果Bessie处在一个给定的位置 $ k $ ,她可以进行下面两项中的任意一项:

    1. 投掷一枚硬币。如果背面朝上,她前往位置 $ k-1 $ ,如果正面朝上,她前往位置 $ k+1 $ (也就是说,每种可能性 $ 1/2 $ 的概率)。

    2. 跳下平衡木,获得 $ f(k) $ 的报酬( $ 0 \leq f(k) \leq 10^9 $ )。

    Bessie意识到她并不能保证结果能够得到某一特定数量的报酬,这是由于她的移动是由随机的掷硬币结果控制。然而,基于她的起始位置,她想要求出当她进行一系列最优的决定之后,她能够得到的期望报酬(“最优”指的是这些决定能够带来最高可能的期望报酬)。

    例如,如果她的策略能够使她以 $ 1/2 $ 的概率获得 $ 10 $ 的报酬,$ 1/4 $ 的概率获得 $ 8 $ 的报酬,$ 1/4 $ 的概率获得 $ 0 $ 的报酬,那么她的期望报酬为加权平均值 $ 10 \times (1/2)+8 \times (1/4)+0 \times (1/4)=7 $ 。

    输入输出格式

    输入格式:

    输入的第一行包含 $ N $ ( $ 2 \leq N \leq 10^5 $ )。以下 $ N $ 行包含 $ f(1) \ldots f(N) $ 。

    输出格式:

    输出 $ N $ 行。第 $ i $ 行输出 $ 10^5 $ 乘以Bessie从位置 $ i $ 开始使用最优策略能够获得的报酬的期望值,向下取整。

    输入输出样例

    输入样例#1: 复制
    2
    1
    3
    输出样例#1: 复制
    150000
    300000
    
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。