P12304 [ICPC 2022/2023 WF] 过桥 题解

· · 题解

容易发现大致的过河策略形如安排几个人负责传送电筒，然后剩下的人只过河一次不再回来。显然过河时间越少的人来回的次数应该越多（否则交换他和一个次数更多但时间更长的人必然更优），因此可以假定前 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)。

代码