传送机 2 / Teleporter 2 JOI Final 2026

[JOI Final 2026] 传送机 2 / Teleporter 2

[JOI Final 2026] 传送机 2 / Teleporter 2。

给定直线 $1\sim n$，以及 $m$ 个区间 $[s_i,t_i)$，要求不交区间的最大个数不超过 $k$。你可以通过花费 $c_i$ 的代价删除区间 $i$。求最小代价。

$n,m,k\le 10^5,c_i\le 10^9$。

首先有一个很厉害的转化：

不交区间的最大个数不超过 $k$，等价于放置 $k$ 个点，使得这 $k$ 个点可以覆盖所有区间。

乍一看挺显然的，但是想到这个真的很难啊！

那么有了这个转化后，我们就可以写出一个简单的 $\mathcal{O}(n^3)$ 的 DP：

定义 $f_{i,j}$ 表示考虑 $1\sim i$，放置了 $j$ 个点的最小代价。那么如果定义 $w(l,r)$ 表示所有完全包含在区间 $[l,r]$ 的区间代价和，那么可以轻松写出转移：

$$f_{i,j}=\min_k\{f_{k,j-1}+w(k+1,i)\}$$

接着考虑优化。观察 $w$ 的性质，发现其实它满足四边形不等式：

考虑证明 $w(l+1,r-1)+w(l,r)\le w(l+1,r)+w(l,r-1)$。

显然对于一个完全包含的区间，有三种情况：

• 完全位于区间 $(l,r)$ 内；
• 只有一端在 $l$ 或者 $r$ 上；
• 区间 $[l,r]$。

那么很显然的，第一类区间会在等式两边都只计算 $2$ 次，二类都只算 $1$ 次，三类只有左边有，于是证毕。

那么这个 DP 具有凸性，再结合不超过 $k$ 个的限制，我们可以使用 wqs 二分解决。

然后，不妨设二分 $w$，则由于使用了 wqs 二分，DP 的第二维可以省去，那么新的转移：

$$f_i=w+\min_j\{f_j+w(j+1,i)\}$$

这样就可以优化到 $\mathcal{O}(n^2\log V)$。

最后使用线段树优化这个 DP 即可。

PS: wqs 二分可能贡献，此时需要取横坐标最小的。