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的路径。

考虑优化，有

结论1：设序列 a 是一个LIS，序列 b 是一个LIS，r_i= \min (a_i,b_i),r_i'=\max(a_i,b_i) ，则 r_i,r_i' 都是一个 LIS

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

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