P15171 [SWERC 2022] 水白子怎么吃井了

Harekaze · 2026-11-13 15:45:58 · 题解

显然 y 是个假的东西。

首先考虑如果每个位置独立往下放积木需要 h 个。而如果 x_1 和 x_2 合并，那么它们能在高度 h-\displaystyle\lceil\frac{x_2-x_1}{2}\rceil 上连在一起，可以节省 h+1-\displaystyle\lceil\frac{x_2-x_1}{2}\rceil 个积木。

考虑最大化这个节省量。设 g_{l,r} 表示将区间 [l,r] 的紫色积木合并成一个块所能节省的最大别色积木数。那么将 [l,k] 和 [k+1,r] 合并能节省的积木就是 h+1-\displaystyle\lceil\frac{x_r-x_l}{2}\rceil 个，因为两区间一定会向中间缩。这样 g_{l,r}=\max_{l\leq k<r}\{g_{l,k}+g_{k+1,r}+h+1-\displaystyle\lceil\frac{x_r-x_l}{2}\rceil\}，注意这里要排除掉无法连在一起的情况。

最后答案显然是一个个块，设 f_i 表示完成支撑前 i 块积木能节省的最大积木量，显然 f_i=\max_{0\leq j<i}\{f_j+g_{j+1,i}\}。

最后答案就是 n\times h-f_n，容易做到 O(n^3)。