Public NOIP Round #8 题解

来源：

最后 bitset 中为 $1$ 的点 $j$ 是在 $i \in [l,r]$ 中 $s_{i,j}$ 全为 $0$ / 全为 $1$ 的。

设 $len_{i,j}$ 表示从 $(i,j)$ 开始往右，相同的的最大长度。这个可以直接递推得出。

将每个 $i$ 的所有 $len_{i,j}$ 排序，查询时二分即可。

来源：

$X_{max} - X_{min}$ 可以看作，选出 $k$ 个点后，在点集中任意选出一个点贡献 $+X$，再任意选一个点贡献 $-X$，得到的最大值。$Y_{max} - Y_{min}$ 也同理。

于是设 $f_{i,j,s}$ 表示前 $i$ 个点中，选了 $j$ 个点，$+X/-X/+Y/-Y$ 有哪些已经选择并产生贡献（状压为 $s$）。可以得到 $O(nk)$ 的做法。

进一步的，考虑贪心：若 $k\ge 5$，容易发现 $c$ 最大的点一定被选。如果不选 $c$ 最大的点，剩下 $5$ 个点中一定存在不对 $+X/-X/+Y/-Y$ 产生贡献的点，可以调整到 $c$ 更大。

这样就把问题降为了 $k\le 4$，DP 部分的复杂度降为 $O(n)$，只需要对 $c$ 排序。时间复杂度 $O(n\log n)$。

来源：

对于最终方案，积水的总体积为：

$$\sum_{k=1}^n\min\{\max_{1\le j\le k}h_j,\max_{k\le j\le n}h_k\}-h_k$$

注意到只与前缀、后缀最大值有关，因此可以 DP：

设 $f_{i,j,p,s,0/1}$ 表示前缀 $i$ 个格子中，选了 $j$ 个抹平，此时前缀最大高度为 $p$，后缀最大高度为 $s$，积水数量 $\bmod 2$ 为 $0/1$。

观察到 $p,s$ 都只有至多 $k+1$ 种取值，状态数为 $O(nk^3)$，转移为 $O(1)$。

考虑优化：注意到，最终最高的格子一定不会贡献任何积水，但是最高的格子可以当作边界来用。

假设枚举了最终最高的格子 $i$，那只需要前缀/后缀分别 DP，在这个位置合并即可。

那么状态降为 $f_{i,j,p,0/1}$（不需要记录后缀最大高度），时间复杂度 $O(nk^2)$。

来源：

Crysfly的博客