自动搬运

查看原文

来自洛谷，原作者为

	pikiuk “Back like I never left!”

搬运于2025-08-24 22:54:25，当前版本为作者最后更新于2024-01-21 22:37:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

irris 的题解太厉害了，我来点不怎么厉害的。

考虑 $m=1$ 的情况，两种极端策略是：

• 我抓住一个一直刀，直到死亡为止。
• 我刀死最小的小怪，如果某只小怪被刀了最小小怪血量次数刀没死，我就换下一只。

继续考虑 $m=1$ 的情况，容易发现我可以在最开始钦定一下我刀死小怪的血量，然后最坏情况下血量大于他的小怪都要被试错他的血量刀数。

仔细思考一下，发现 $m>1$ 也可以这么做，具体的，我们把 $\{a_n\}$ 排序，考虑如果我们钦定了若干小怪 $\{b_m\}$，最后死亡的是 $a_{b_{1\sim m}}$ 的时候我们最坏情况需要的代价。

不难发现根据之前的分析下标在 $(b_k,b_{k+1})$ 的小怪要被试错 $a_{b_{k}}$ 刀，很容易依次设计状态：$f(i,j)$ 表示当前考虑到 $a_i$，确定了 $b_{1\sim j}$ 且 $b_j=i$ 时最坏情况需要的代价。转移的时候枚举 $b_{j-1}$ 转移，有：

这个式子不难用斜率优化优化，时间复杂度 $\mathcal{O}(n^2)$。