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

首先考虑一个暴力的思路。我们枚举 $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)$，跑不满，可以轻松通过。图画得可能比较抽象。