题解：P17140 [NOI 2026] 线段（暂无数据）

T0mle · 2026-07-24 21:23:38 · 题解

简单题，场上为什么 1.5h 才过。

容易发现线段集合优美的条件为：线段的并是一段区间，每个点最多被两条线段覆盖。

容易想到按照 l 的大小加入线段，随便写出 dp：f_{i,j,k} 表示线段右端点最大值为 i，次大值为 j，共有 k 条线段的方案数。

加入一条线段 [l,r]，对于 f_{i,j,k}(j<l\le i) 有如下转移：

• 若 r\ge i，f_{r,i,k+1}\gets f_{i,j,k}；
• 若 r<i，f_{i,r,k+1}\gets f_{i,j,k}。

发现 j 这一维可以前缀和优化掉，k 这一维可以滚动。

时间复杂度 O(nmk)，空间复杂度 O(m^2)。