P1410 子序列题解

Steadywelkin · 2021-05-10 11:54:10 · 题解

这里提供一个运用 Dilworth 定理的方法

Dilworth 定理

给定一个偏序关系，比如一个数出现的位置 i 在另一个数出啊先的位置 j 之前，并且满足 a_i>a_j ，那么这个满足这个偏序关系的序列就称为链，关于链和反链的定义：

链：一个偏序集 S 的全序子集（全序是指任意两个元素可以比较）

反链：一个偏序集 S 的子集，其中任意两个元素不可比较

最大链的长度等于最少反链覆盖数，最大反链长度等于最少链覆盖数

所以对于本题而言，我们可以先对于整个序列求一次最长反链，也就是最长不上升子序列的长度（下面设为 len ），分类讨论：

如图所示，当 len=2 的时候，必然是因为在序列中 pos 前后的两部分均为严格上升，只有个位置 pos 出现了“断层”的情况，在这个位置 pos 上，值域可以为 [up,down] ，现在我们考虑将严格上升的部分划分出一部分给这个特殊位置 pos ，使得两个序列的长度均为 \begin{aligned}\frac{n}{2}\end{aligned}

我们将 a[pos] 的值横向映射过去，显然如果要划分子序列，图中 len 的部分是不能划分给 pos 所在的子序列的，因为要保证序列的严格上升，那么就可以得到：

（1）如果 \begin{aligned}len\le\frac{n}{2}\end{aligned} 那么可以通过划分将原序列分为两个严格上升子序列
（2）如果 \begin{aligned}len>\frac{n}{2}\end{aligned} 那么在 pos 前的一个序列长度就已经超过了 \begin{aligned}\frac{n}{2}\end{aligned} ，显然这种情况是不能划分的

但是这样划分还是不完备的，如下图：

虽然映射之后的 len 是不到 \begin{aligned}\frac{n}{2}\end{aligned} 的，但是很显然，这种情况也是不可能划分的，因为后面的部分不能划分到前面 len1 的部分，所以对于上面的第 2 中情况还要将 len1 len2 求出（注意这里的 len2 的长度是指低于第一部分的最高点的最高位置到 pos 的长度，包含 pos），有（在上面 2 的条件下）：

否则有解

至于 pos 的具体位置，因为其他位置都满足单调性，可以直接 O(n) 扫一遍找到

寻找映射到的位置可以通过二分查找，时间复杂度 O(logn)

加上前面的寻找最长不上升子序列的 O(nlogn) ，总时间复杂度为 O(nlogn) ，可以通过此题

P1410 子序列 题解

P1410 子序列题解