自动搬运

查看原文

来自洛谷，原作者为

	cmk666 伊娜可爱捏 伊娜贴贴捏

搬运于2025-08-24 22:59:44，当前版本为作者最后更新于2024-06-19 09:05:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

sub 1

直接贪，能往右方就往右放。

sub 2,3

状态数只有 $O(2^ln)$，直接爆搜。

sub 4

到这个开始就比较有脑子了。

考虑对于每个人，我们只关心的状态是：她是向左，还是向右，还是贡献到答案。那么一个状态合法，当且仅当：不存在一个医院接受了 $>c_i$ 个人；也不存在一个人在两边的医院至少有一个有空位的时候算入答案。

容易发现 check $i$ 医院是否合法的时候，只要用到 $i-1$ 和 $i$ 位置的人的决策。据此 dp 即可。而由于 $c_i=1$，一条路上只有前 $2$ 个人是有用的，后面的人必然是算入答案的，那么状态数就是常数的，直接做就是线性。

sub 5

没了 $c_i$ 的限制，上面的 dp 状态数都是指数级的，做不了一点。但是我们仍然可以沿用类似的 dp 思路。

事实上，check $i$ 的时候没必要记录所有人的决策。考虑定义 dp 状态 $dp_{i,j,k}$ 表示：当前到第 $i$ 条路，往第 $i+1$ 个医院送了 $j$ 个人，且第 $i+1$ 个医院将会在 $k$ 时刻变满，或者当 $k=n+1$，表示永远不满。

转移的时候直接枚举 $dp_{i+1,j',k'}$，那么若 $k'>k$，则第 $i+1$ 条路上 $(k,k']$ 的人都要往右送，也就是限制了 $j'$ 的一个下界；同时，记 $x=$ 第 $i+1$ 条路上 $[1,\max(k,k')]$ 中的人数，那么容易得到往左送的人数为 $x-j'$，于是对于医院 $i+1$ 有 $x-j'+j\le c_{i+1}$，当且仅当 $k\ne n+1$ 时取等。然后还有一些边界上的特判，是 trivial 的。

由于 $i,j$ 两维的总和是 $O(n)$ 的，于是状态数是 $O(n^2)$ 的，加上一些煎蛋的预处理后，直接暴力转移复杂度为 $O(n^4)$，可以通过 sub 5。实现的时候需要把不合法位置及时赋值为 $-\infin$ 避免影响答案，然后如果你不想写 std::vector 这种动态开空间的东西需要滚动数组，注意每次清空的大小。

sub 6

状态数已经足够优秀，考虑减少转移次数。

考虑转移时的这个条件（$x$ 定义同上）：对于医院 $i+1$ 有 $x-j'+j\le c_{i+1}$，当且仅当 $k\ne n+1$ 时取等。

那么可以发现，对于一对固定的 $(j',k')$，只有 $O(n)$ 对 $(j,k)$ 可以转移到她！原因是：

• 若 $k\ne n+1$，则上式取等，得到 $j=c_{i+1}-x+j'$，那么枚举 $k$ 便能确定 $x$ 进而 $j$ 只有唯一的一种可能，于是共有 $O(n)$ 个转移；
• 若 $k=n+1$，那么枚举 $j$，也只有 $O(n)$ 个转移。

那么转移的复杂度被降到了 $O(n)$，总复杂度 $O(n^3)$。

sub 7&8

对于 $x$ 的定义中含有 $\max(k,k')$，很麻烦，不妨拆之。也即，把转移分成三种：$k\le k'$、$k'\le k\le n$ 和 $k=n+1$（这种是上一个 sub 拆出来的）。容易发现她们都是求上一层 dp 数组的区间 $\max$，直接上线段树，复杂度 $O(n^2\log n)$，可以通过 sub 7。

更进一步的，观察到有一个端点是只跟某个下标相关的，于是实质上求的是前后缀 $\max$，没必要使用线段树。于是可以做到时空复杂度 $O(n^2)$，至此得以通过此题，完结撒花！