Qoj2570. Maximal Subsequence

Qoj2570. Maximal Subsequence

给定一个包含 $n$ 个整数的数组 $a$。序列的美观度定义为该序列的最长递增子序列的长度。要求找出数组 $a$ 的一个子序列，使得该子序列的美观度小于整个数组 $a$ 的美观度，并且该子序列的长度尽可能大。

转化题意，找出子序列等价于在原序列上删数，所以问题等价于删去最少的数，使新序列的LIS长度减小。

首先，转化为最小割问题。设 $f_i$ 表示以 $i$ 结尾的LIS的长度。当$f_i=f_j+1$ 且 $j<i$ 时，$i$ 可以放在LIS中，所以 $j$ 向 $i$ 连边。当 $f_i=l(LIS长度)$ 时，$i$ 向 $T$ 连边，当 $f_i=1$ 时，$j$ 向 $S$ 连边。 考虑如何表示删点，将每个点拆开，变成 $l_i,r_i$ ，原来的建图变为 $(r_j,l_i,inf)$，两个点之间连1，即 $(l_i,r_i,1)$。

最小割值等于最大流，所以我们就要求出这张图的 $S \to T$ 的最大流。这就是选择尽可能多的 $S \to T$的路径。

考虑优化，有

如图，红色是一个LIS，黄色是一个LIS，绿色就是 $r_i$，也是一个LIS，下面三个点就是 $r_i'$，也是 LIS。

所以，就可以设计算法: 每次只保留构成LIS的点。 每次我们就选绿色圈起来的部分，这一定是一条LIS，虽然在DP时我们的LIS会像橙色和紫色一样歪歪扭扭，但我们取绿色来算一定正确。注意每次删完绿色的点后原来保留下的点会不成立，也要删去。