[CF2133D] Chicken Jockey 题解

Upd. 修了一点笔误。

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

首先攻击的形式一定钦定若干个生物，打死这些生物，使得剩下的生物形成若干个堆叠。对于每个堆叠，我们再从下往上依次一个个打死。容易发现，若 是一个独立的堆叠，需要的攻击次数是 ，减一与加一是因为除了第一个生物都会受到 的跌落伤害。设前缀和数组为 ，那么上式就是 。

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

答案是 。上式的具体含义是：打 次把第 个生物打死，第 个生物受到 点跌落伤害后还需要打 次，接下来区间 的生物每个生物都会受到 点跌落伤害，需要打 次。

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

这个 DP 是 的，考虑优化。发现 与 是互相独立的，所以把 与 拆开变为：

所以实时记录 的 中 的最小值即可。时间复杂度 。

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