joi open t2

cmk666 · 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)，至此得以通过此题，完结撒花！