P8816 [CSP-J 2022] 上升点列 题解

· · 题解

P8816

提供一种不一样的做法。

首先将每个点以横坐标为第一关键字，纵坐标为第二关键字排序。

一维的 dp 肯定不够，因为 dp 既要存最多点数，又要保存自由点的点数。

赛时没看 k 的范围，于是开了一个结构体。

从其左下部分的点转移即可。 但如果直接转移，这个 dp 的正确性无法保证，即左部点稀疏而右部点稠密时就会出错。 枚举一个起点 $st$，就可以保证 dp 的正确性了。 因为原 dp 出错只能是该点到起点的距离太长，以至于连接后面的稠密点时，自由点不足，此时正解的所选点都在右部的稠密点。 而枚举起点则确定了剩余的所选点只能在右部，相当于枚举了右部点，解决了左疏右密的问题。 时间复杂度：$\mathcal{O}(n^3)

评测记录