P1410 子序列——dp但是没想到

li_cat · 2025-08-21 13:39:02 · 个人记录

这一题不知道为啥卡了好久

初见思路

题目是要把序列划分成两个集合，每个集合内部满足 i<j \iff a_i<a_j

然后就转化成了两个集合中不存在逆序对

也就是说存在逆序对的两个点不能在一个集合内

于是转化成了图论问题

最开始用并查集，一个连通块内的点不能在一个集合里

结果这个结论是错的，只有直接连通的才不能在一个集合里，这个时候连通分量并没有原来的意义

然后不难想到二分图，但是那个背包真没看懂

dp

考虑描述一个子问题需要什么必要条件

首先根据题目要求，两个子序列的长度需要知道

其次因为要上升，需要记录最后一位保证合法性

以及阶段的一维

但是可以压一下：

• 每个元素必然属于其中一个集合，所以阶段的那一维和两个长度的和是相等的，压掉一维
• 同上可知，枚举到 i 时必然有一个子序列的末尾是 a_i ，所以其中一个也可以压掉
• 但是现在一看，这个状态里面存的是什么呢，bool太浪费了，根据贪心的思想，要让另一个子序列的末尾最小，可以令这个状态里存另一个子序列的最小末尾

于是真正能使用的状态就出现了

• a_i$ 给了第二个子序列，这个时候两个子序列要交换一下，即 $dp_{i,j}=a_i-1$ $[a_i>dp_{i-1,i-j-1}]

然后还有一个从 j=0 来的特判，因为 j=0 时并不会判断合法性，所以接上第二个子序列的时候要判定前方是否合法