自动搬运

查看原文

来自洛谷，原作者为

	qiuzx GGMU

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

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

以下是正文

容易发现大致的过河策略形如安排几个人负责传送电筒，然后剩下的人只过河一次不再回来。显然过河时间越少的人来回的次数应该越多（否则交换他和一个次数更多但时间更长的人必然更优），因此可以假定前 $r$ 小的人被安排传送电筒，称他们为关键的人。则对于剩下的人，可以看作每次选择 $0\le t\le c$ 个，将他们以及至多 $c-t$ 个关键的人送至对面，然后再回来一个关键的人。若记 $s$ 表示对面关键的人个数，则选择一次 $t$ 可以看作给 $s$ 增加了 $c-t-1$，要求保证 $s$ 时刻非负且不大于关键的人数。

假如已经确定了每次需要传送的人数 $t$，那么怎么安排最优呢？显然将所有 $t$ 按照大小排序之后记为 $t_1\le t_2\le\cdots\le t_k$，则必然是将不关键的人前 $t_1$ 个一组，接下来的 $t_2$ 个分一组，一直到最大的 $t_k$ 个人分一组最优。此外我们可以任意安排 $t_i$ 的顺序，而只有在 $t=c$ 的时候才可能使得 $s$ 减小，所以非负性是更好满足的。这样可以看作每次随便选一个 $t_i<c$ 的操作一次，然后一直做 $t_i=c$ 的操作直到把对面的人清空。考虑到这里选择 $t_i$ 的顺序不是很重要，所以可以认为是按照 $t_1,t_2,\cdots$ 这样从小到大的顺序依次选择的。

有了上面这个分析的过程，容易发现任意时刻在对面的非关键人一定形如一段前缀加一段后缀（当然是去除了关键人之后），且后缀的人数必然是 $c$ 的倍数（因为每次操作后缀都一定取 $t=c$）。那么关键的人又如何呢？注意到我们是按照 $t_i$ 从小到大的顺序操作的，而每次操作显然应该尽可能多地将关键的人送到对面（即使 $t=0$ 也是如此，因为此时虽然送更少的人可能可以减小代价，但反正后面的人最后也得运过去，所以不如一起运走）。因此往对面运的人数必然是越来越少的。同时每次向后运一定是运最小的人更优，这意味着如果一个人在某一步没有被运到对面，那么他永远也不可能被运过去了，但这是不可能的。所以只能是每一次操作都把所有剩余的关键的人运走，只不过这些人中有一些之后不会再回来了。这也间接说明了关键的人数必然不超过 $c$，否则第一步无法将所有人都运走。

这样任意时刻在对面的人必然形如一段区间加一个后缀，满足这个区间左端点 $\le c$，且后缀长度为 $c$ 的倍数。而一次操作要么把左端点拓展到 $1$ 并可能将右端点向右移动若干位，要么将左端点向右一位，并将后缀长度增加 $c$。这样可以直接暴力 dp 记 $f_{i,j,k}$ 维护区间以及后缀的端点，由于 $i\le c,k\equiv n\pmod c$，所以总状态数 $O(n^2)$。可以使用前缀 $\min$ 优化转移做到 $O(1)$，总复杂度 $O(n^2)$。

代码