题解：P12767 [POI 2018 R3] 围栏 Fence

Monomial · 2025-11-17 20:36:55 · 题解

首先考虑一个暴力的思路。我们枚举 y 最小的点，然后按极角排序，设 DP 状态 f_{i,j} 表示我们凸多边形的前两个点是 i,j 两个点，目前的凸多边形价值的最大值，需要预处理 i,j 两个点与最低点形成的三角形内所有点的价值和 val_{i,j}，单次 DP 和预处理贡献都是 \mathcal{O}(n^3) 的，那么总复杂度就是 \mathcal{O}(n^4) 的。

接下来考虑优化这个做法。枚举最低点的过程显然是不太能去掉的，于是我们考虑优化转移的过程和 val 的求值。

先思考如何优化 val 的求值。

我们考虑固定 i，尝试快速求出 val_{i,j} 的取值。我们将对最低点极角排序后排名在 i 之后的点拉出来，再做一次极角排序，对于一个 j，其他的点 k 能对 val_{i,j} 产生贡献的条件是，len_{i,k} < len_{j,k} 且保证 k 在新的极角排序中的排名大于 j（不合法情况参见上图），那么我们按 len_{i,j} 排序后，用 BIT 维护排名小于某个值的 w_j 之和即可，单次 val 的取值的时间复杂度优化到了 \mathcal{O}(n^2 \log n)。

接下来考虑优化转移。

对于连续的三个点 i,j,k，其合法可以视作，若按极角排序，那么 j,i 边的反向延长线的排名小于 j,k 边的排名。那么我们枚举中间点转移，然后排序后维护前缀 \max 值即可，单次时间复杂度也是 \mathcal{O}(n^2 \log n)。

那么总的时间复杂度就是 \mathcal{O}(n^3 \log n)，跑不满，可以轻松通过。图画得可能比较抽象。