[CF2133D] Chicken Jockey 题解

· · 题解

Upd. 修了一点笔误。

显然是 DP，并且是稍微想一想就能发现性质的 DP。

首先攻击的形式一定钦定若干个生物，打死这些生物，使得剩下的生物形成若干个堆叠。对于每个堆叠，我们再从下往上依次一个个打死。容易发现，若 [l, r] 是一个独立的堆叠，需要的攻击次数是 1 + \sum_{i = l}^r h_i - 1，减一与加一是因为除了第一个生物都会受到 1 的跌落伤害。设前缀和数组为 s，那么上式就是 s_r - s_{l - 1} - (r - l)。

注意到，为了减少攻击次数，我们会尽量增加摔落伤害。要增加摔落伤害，我们会从上往下打死钦定的生物。所以考虑倒着 DP，设 dp_i 表示 i 是钦定的生物之一，打死 [i, n] 的生物的最少操作次数。初始状态是 dp_{n + 1} = 0。有转移：

dp_i = \min_{j = i + 2}^{n + 1}\{dp_j + h_i + \max(0, h_{i + 1} - i) + s_{j - 1} - s_{i + 1} - (j - i - 2)\}

答案是 dp_1。上式的具体含义是：打 h_i 次把第 i 个生物打死，第 i + 1 个生物受到 i 点跌落伤害后还需要打 \max(0, h_{i + 1} - i) 次，接下来区间 [i + 2, j - 1] 的生物每个生物都会受到 1 点跌落伤害，需要打 s_{j - 1} - s_{i + 1} - (j - i - 2) 次。

这个转移方程漏掉了 j = i + 1 的情况，但是发现 j = i + 1 时显然不优，所以也不用分讨。

这个 DP 是 O(n^2) 的，考虑优化。发现 j 与 i 是互相独立的，所以把 i 与 j 拆开变为：

dp_i = \min_{j = i + 2}^{n + 1}\{dp_j + s_{j - 1} - j\} + h_i + \max(0, h_{i + 1} - i) - s_{i + 1} + i + 2

所以实时记录 \ge i + 2 的 j 中 dp_j + s_{j - 1} - j 的最小值即可。时间复杂度 O(n)。

赛时提交记录，这份代码中答案取的是 dp_0，但并不影响。