【DP 凸优化】P15944 [JOI Final 2026] 传送机 2 / Teleporter 2 笔记

题意相当于删除一些区间，使得任意选择不交（端点除外）区间，没有超过 $K$ 个的方案。

有个牛逼的转换是在数轴上选 $K$ 个点，将不包含这些点的区间全部删去。

然后就可以设计一个 DP，设 $f_{i,j}$ 表示考虑前 $i$ 个点，已经放置了 $j$ 个关键点的最小代价，有 $f_{i,j}\leftarrow \underset{k<i}{min}\{f_{k,j-1}+w(k,i)\}$，其中 $w(l,r)$ 表示摧毁被 $(l,r]$ 完全包含的区间的代价和，时间复杂度 $O(n^3)$。

通过将被包含的区间的左右端点进行分类，我们发现 $w(l,r)$ 满足四边形不等式，因此二分队列可以优化到 $O(n^2\log n)$。

但是这样还不够，考虑四边形不等式的其他性质，可以利用 $g(j)=f_{i,j}$ 关于 $j$ 有凸性，那么使用 WQS 二分就可以变成 $f_i\leftarrow \underset{j<i}{min}\{f_j+w(j,i)+\lambda \}$，时间复杂度 $O(n^2\log V)$。

看到这个 $min$ 明显指向数据结构优化，恰好 $w([1,j],i)\to w([1,j],i+1)$ 的变化是区间加，因此使用线段树优化 DP 即可做到 $O(n\log n\log V)$。