粉刷栅栏 题解

思路

考虑一段连续木板，设它们已经共同刷到了高度 $h$。有两种选择：逐块竖刷，代价是区间长度；或者先把整段水平刷到区间最小高度 $m$，代价为 $m-h$，再递归处理所有高度大于 $m$ 的连续子段。两者取较小值即为最优，因为任何水平描边在首次遇到区间最低木板后都不可能继续抬高整段。

直接递归时，每层扫描最小值，单调高度会导致平方复杂度。所有递归区间恰好对应最小笛卡尔树的子树：节点是当前区间最小木板，左右儿子对应它两侧的子区间。

做法

子任务 1 可把区间、已刷高度作为状态，枚举竖刷或继续水平刷并记忆化。

子任务 2 按上述递归式，每次线性寻找区间最小值并划分连续子段。

完整做法用单调栈建立最小笛卡尔树。设节点 $u$ 的子树木板数为 $sz_u$，父节点高度为 $b$，则

$$dp_u=\min\bigl(sz_u,\ a_u-b+dp_{left}+dp_{right}\bigr).$$

空儿子贡献为 0。根节点的父高度视为 0。

复杂度

子任务 1 的状态数为 $O(n^3)$，朴素转移时间为 $O(n^4)$，空间复杂度为 $O(n^3)$。

子任务 2 的最坏时间复杂度为 $O(n^2)$，递归空间复杂度为 $O(n)$。

完整做法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。