自动搬运

查看原文

来自洛谷，原作者为

	Cry_For_theMoon **

搬运于2025-08-24 22:14:35，当前版本为作者最后更新于2021-07-04 08:13:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门

提供一个更加优越的做法。

首先想到暴力，设 $f(i,j,k,0/1)$ 是第 $i$ 台机器做 $j$ 个 $A$ ，$k$ 个 $B$，最后做的一个任务是 $A/B$ 的最少时间。$O(n^3p)$ 预处理后继续设 $g(i,j,k)$ 是前 $i$ 台机器分配 $j$ 个 $A$，$k$ 个 $B$，最慢完成的机器的完成时间的最小值。正常背包即可，但这部分复杂度高达 $O(n^4p)$. 虽然最后还是 AC 了，但是 2001 年的机子显然没有今天这么快，也就是说正解很可能并不是暴力背包。

同样设 $f(j,k)$ 是某台机器做 $j$ 个 $A$，$k$ 个 $B$ 的最少时间。

引理：固定 $j$ 后 $f(j,k)$ 是单谷的

对，看上去非常反人类，为什么 $f(j,k)$ 还会比 $f(j,k+1)$ 要慢。（其实样例里第 $1$ 台机器在 $j=4$ 的时候就是这样）题目里唯一不舒服的地方就是那个“处理连续同类任务所需时间是系数乘以任务数目的平方”。我们知道平方增长是非常快的，所以很容易想到

变成了

如果 $A$ 的执行系数 $k_A$ 特别高昂而执行 $B$ 的代价特别低廉，我们就用了执行一次 $B$ 的代价把一个 $16K_A$ 变成了 $8K_A$. 那显然代价会更小。

所以这个反人类的东西确实可能成立。但是我们怎么说明其单谷呢。首先考虑除了切割 $A$ 还有没有别的形式使得添加一个 $B$ 后代价更加低廉，我们得到的结论是“没有”。证明如下：

首先证明，如果 $B$ 和其它早就有的 $B$ 合在一起，那么 $f$ 是不会变小的。这是因为如果最后 $f$ 较添加前变小，去掉这个 $B$ 的 $f$ 应该更小，矛盾了。

那么这个 $B$ 只可能单独为一段，才有可能更优秀。它影响不到别的 $B$ 的答案，只能影响 $A$ 的答案来让 $f$ 变小。而影响 $A$ 的答案，对于 $B$ 来说，除了切割没有别的方法。证毕。

然后考虑说明其单谷性：

如果 $f$ 不断上升，说明 $B$ 对 $A$ 的切割不再有效，此时后面 $f$ 不再会下降。

所以如果开头 $f$ 就上升，那么它就是不断上升的；如果开头 $f$ 下降，要么它也不断下降上去，要么下降到一个点，开始上升，然后不断上升下去。所以 $f$ 是单谷函数。证毕。

“这个引理想到后这个题就差不多了。”

确实，因为我们不难想到二分耗时机器最大的那台的最早结束时间。然后对于每台机器，确定了其 $A$ 的台数，其最大能执行的 $B$ 的台数是可以确定的。也就是说有 $O(np)$ 个状态，然后继续设 $g(i,j)$ 是前 $i$ 个机器共做 $j$ 台 $A$ 能同时做的最大的 $B$ 的数目。这个东西的确定就是 $O(pn^2)$ 的。所以我们在 $O(pn^2 \log n)$ 的时间内解决了这个问题。

代码就不放了。

还是暴力香吧。