P6688: 平衡木
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
Bessie为了存钱给她的牛棚新建一间隔间，开始在当地的马戏团里表演，通过在平衡木上小心地来回走动来展示她卓越的平衡能力。
Bessie能够通过表演赚到的钱取决于她最终成功跳下平衡木的位置。平衡木上从左向右的位置记为0,1,…,N+1。如果Bessie到达了位置0或是N+1，她就会从平衡木的一端掉下去，遗憾地得不到报酬。
如果Bessie处在一个给定的位置k，她可以进行下面两项中的任意一项：
1. 投掷一枚硬币。如果背面朝上，她前往位置k−1，如果正面朝上，她前往位置k+1（也就是说，每种可能性1/2的概率）。
2. 跳下平衡木，获得f(k)的报酬（1≤f(k)≤109）。
Bessie意识到她并不能保证结果能够得到某一特定数量的报酬，这是由于她的移动是由随机的掷硬币结果控制。然而，基于她的起始位置，她想要求出当她进行一系列最优的决定之后，她能够得到的期望报酬（“最优”指的是这些决定能够带来最高可能的期望报酬）。例如，如果她的策略能够使她以1/2的概率获得10的报酬，1/4的概率获得8的报酬，1/4的概率获0的报酬，那么她的期望报酬为加权平均值10(1/2)+8(1/4)+0(1/4)=7.
输入格式（文件名：balance.in）：
输入的第一行包含N（2≤N≤105）。以下N行包含f(1)…f(N).
输出格式（文件名：balance.out）：
输出N行。第i行输出105乘以Bessie从位置i开始使用最优策略能够获得的报酬的期望值，向下取整。
输入样例：
2
1
3
输出样例：
150000
300000