题解：CF2021D Boss, Thirsty

baoyangawa · 2024-10-19 18:01:40 · 题解

part 1. 状态设计

若第 i-1 天选择的区间为 [L, R]，则第 i 天的选择 [l, r] 至少满足以下两个条件之一：

l < L \le r
l \le R < r

也就是说，覆盖左端点并至少向左超出一个，或者覆盖右端点并至少向右超出一个。

于是，我们设计一个关于左右端点的状态：

对于第一行特殊处理，因为第一行可以选择长度为 1 的区间。

对于第 i > 1 行，我们做如下转移：

枚举区间 [l, r]，满足 l < r；
计算 V = \max \Big((\max\limits_{p=l+1}^{r} f_{i-1,p}), (\max\limits_{p=l}^{r-1}g_{i-1,p})\Big) + \operatorname{sum}(l, r)，容易证明这样能取遍符合条件的，i-1 行区间的选择。其中 \operatorname{sum}(l, r) 为第 i 行，第 l 到第 r 列的和。
用 V 更新 f_{i,l} 和 g_{i,r}。

暴力枚举 p 可以做到 O(nm^3)，加上一点前缀和优化可以做到 O(nm^2)。

Part2. 优化

我们单拎出来 f_{i, j} 的转移。

f_{i,j} = \max_{k=j+1}^{m}\Bigg(s_k - s_{j-1} + \max\Big((\max_{p=j + 1}^{k}f_{i-1,p}), (\max_{p=j}^{k-1}g_{i-1,p})\Big)\Bigg)

考虑对这个式子优化。

\Big(\max_{k=j+1}^{m}(s_k + \max_{p=j + 1}^{k}f_{i-1,p})\Big), \Big(\max_{k=j+1}^{m}(s_k + \max_{p=j}^{k-1}g_{i-1,p})\Big) \Bigg)

尝试把关于 p 的枚举，上下标统一：

{\color{red}\max_{k=j+1}^{m}(s_k + f_{i-1,k})}, {\color{blue}\max_{k=j+1}^{m}(s_k + g_{i-1,j})}, {\color{green}\max_{k=j+1}^{m} (s_k + \max_{p=j+1}^{k-1}\max(f_{i-1,p}, g_{i-1,p})) } \Bigg)

考虑在 j 从右往左扫的过程中，红蓝两部分可以直接维护，问题就在于绿色部分。

实际上绿色部分中内层 \max 还可以往外提：

\max_{k=j+1}^{m} \max_{p=j+1}^{k-1}(s_k + \max(f_{i-1,p}, g_{i-1,p}))

更换枚举顺序：

\max_{p=j+1}^{m-1} \max_{k=p+1}^{m}(s_k + \max(f_{i-1,p}, g_{i-1,p}))

然后就可以把 \max(f_{i-1,p},g_{i-1,p}) 提出去：

\max_{p=j+1}^{m-1} \Big(\max(f_{i-1,p}, g_{i-1,p}) + \max_{k=p+1}^{m}s_k \Big)

然后就会发现，j 向左移动到 j-1 时，只会增加如下贡献：

\max(f_{i-1,j}+g_{i-1,j}) + \max_{k=j}^{m}s_k

这东西只需要维护 s_k 的后缀最大值，就可以 O(1) 计算了。

对于 g 的转移，可以考虑直接把一行翻转，就能和 f 一样转移了。

总时间复杂度 O(nm)。

提交记录。代码中使用 red 等变量名表示这里转移式中不同颜色的贡献。