P9889 [ICPC 2018 Qingdao R] Plants vs. Zombies

BaoBao 和 DreamGrid 正在玩游戏《植物大战僵尸》。在游戏中，DreamGrid 种植植物来保护他的花园免受 BaoBao 的僵尸攻击。  《植物大战僵尸（？）》 （图片来自 pixiv。ID: 21790160；艺术家：socha） DreamGrid 的花园里有 $n$ 株植物，按一条直线排列。从西到东，植物从 1 到 $n$ 编号，第 $i$ 株植物位于 DreamGrid 的房子东边 $i$ 米处。第 $i$ 株植物的防御值为 $d_i$，生长速度为 $a_i$。最初，所有 $1 \le i \le n$ 的 $d_i = 0$。 DreamGrid 使用一个机器人来浇灌植物。机器人最初在他的房子里。在一次浇水步骤中，DreamGrid 会选择一个方向（东或西），机器人沿该方向正好移动 1 米。移动后，如果第 $i$ 株植物位于机器人的位置，机器人将浇灌植物，并将 $a_i$ 加到 $d_i$ 上。由于机器人的水是有限的，最多可以进行 $m$ 步。 花园的防御值定义为 $\min\{d_i | 1 \le i \le n\}$。DreamGrid 需要你的帮助来最大化花园的防御值并赢得比赛。 - 每次机器人必须在浇灌植物之前移动； - 机器人可以移动超过 $n$ 米到房子东边，或者移回房子，甚至移动到房子西边。

无

无

在下面的解释中，`E` 表示机器人从当前位置向东移动 1 米，`W` 表示机器人从当前位置向西移动 1 米。 对于第一个测试用例，一个候选方向序列是 $\{E, E, W, E, E, W, E, E\}$，这样我们有 $d = \{6,6,12,6\}$ 在浇水后。 对于第二个测试用例，一个候选方向序列是 $\{E, E, E, E, W, E, W, E, W\}$，这样我们有 $d = \{10, 10, 4\}$ 在浇水后。 题面翻译由 ChatGPT-4o 提供。