题解：P17140 [NOI 2026] 线段

· · 题解

前情提要

本题解讲的较为详细，但可能对大佬来说有点啰嗦了，不喜勿喷！

注意到构成的图是一个树可以转换为线段 [l_i,r_i] 与恰好一个线段有交点，考虑 DP。

直接转移需要在左右两个端点进行枚举，不好转移。为了方便转移，我们考虑将线段按左端点从左到右排序，如果左端点相同则按右端点升序排序。

然后按顺序遍历线段，这样可以做到不用考虑左端点。

我们再次分析该线段与恰好一个线段有交点这个性质，通过画图：

黑色线段是已经添加的，蓝色线段是还未添加的，我们发现只有当蓝色线段被【已经添加进去的线段中 r 最大的线段】包含且不与第二长的相交，或成为 r 最大的线段，否则都是不合法的。

因此，我们考虑定义 f_{i,j,k} 表示选择 i 个线段，最大的 r 为 j，次大的为 k 时的方案数。

对于包含关系，有转移：f_{i,j,r_p}=\sum\limits_{1\le k< l_p}dp_{i-1,j,k}，有前提条件 r_p\le j；

对于相交关系，有转移 f_{i,r_p,j}=\sum\limits_{1\le k<l_p}dp_{i-1,j,k}，有前提条件 l_p\le j\le r_p；

可以直接按顺序线段枚举即可，如果不选择 f_{i,j,k}=f_{i,j,k}。

时间复杂度 O(nm^2k)，空间复杂度 O(m^2k)，都会爆炸。

首先将第一维滚动数组优化掉，空间限制满足条件；然后对于求和的部分有限制 1\le k<l_p 考虑前缀和优化，变成 O(1) 修改，时间复杂度 O(nmk)，可过。

corner case 是 k=2 的初始化。

代码，怎么这么好写，20min 就写完了，这下该拜我了。