Balance Beam

题目描述

为了攒钱在牛棚里建一个新摊位，奶牛 Bessie 开始在当地马戏团表演，她小心翼翼地在高架平衡木上来回走动，展示她惊人的平衡感！ Bessie 在表演中赚到的钱与她最终从平衡木上跳下的位置有关。 平衡木从左到右标记为 $0, 1, \ldots, N+1$。 如果 Bessie 走到 $0$ 或 $N+1$，她会从平衡木的一端掉下去，并且很遗憾拿不到任何报酬。 如果 Bessie 处在某个位置 $k$，她可以进行以下两种操作之一：

1. 抛硬币。如果是反面，她移动到位置 $k-1$；如果是正面，她移动到位置 $k+1$（即两种情况的概率均为 $\frac{1}{2}$）。
2. 从平衡木上跳下并获得报酬 $f(k)$ $(0 \leq f(k) \leq 10^9)$。 Bessie 意识到她可能无法保证得到某个确定的报酬结果，因为她的移动由随机的抛硬币决定。 不过，根据她的起始位置，她希望确定：如果她采取一系列最优决策（“最优”指这些决策能使期望报酬尽可能大），她的期望报酬是多少。 例如，如果她的策略以概率 $1/2$ 获得报酬 $10$，以概率 $1/4$ 获得报酬 $8$，以概率 $1/4$ 获得报酬 $0$，那么她的期望报酬是加权平均 $10(1/2) + 8(1/4) + 0(1/4) = 7$。

输入格式

输入格式（文件 balance.in）： 输入第一行包含 $N$（$2 \leq N \leq 10^5$）。接下来的 $N$ 行每行包含一个数，分别为 $f(1) \ldots f(N)$。

输出格式

输出格式（文件 balance.out）： 输出 $N$ 行。第 $i$ 行输出：当 Bessie 从位置 $i$ 出发并以最优策略进行时，其期望报酬的 $10^5$ 倍，并向下取整到最接近的整数。

2
1
3

150000
300000

提示

题目致谢：Franklyn Wang 和 Spencer Compton

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum