

$6.$最长不下降子序列问题

题目

给定正整数序列x1,...,xn 。 （1）计算其最长不下降子序列的长度s。 （2）计算从给定的序列中最多可取出多少个长度为s的不下降子序列。 （3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长度为s的不下降子序列。 设计有效算法完成（1）（2）（3）提出的计算任务。

题解

第一问

可以直接用 $O(n^2)$ 的 $DP$ 来做。 设 $f[i]$ 表示以 $i$ 位置为结尾的最长不下降子序列。 然后转移很简单。 第一问的答案为 $max{f[i]}$，设为 $K$。

第二问

使用网络流解决，使用一种分层图的思想进行状态转移。 将每一个点 $u$ 分成左右的两个点 $u1, u2$，然后由 $u1$向 $u2$ 连一条容量为 $1$的边，这是为了保证每一个点最多只能使用一次，对于所有满足 $f[i] = 1$ 的位置 $i$, 由 $S$ 点向 $i1$ 连边，对于所有满足 $f[i] = K$ 的位置 $i$，由 $i2$ 向 $T$ 连一条容量为 $1$ 的边，此时到了进行模拟转移的时候，对于一个位置 $i$，找到所有位置 $j$，满足 $j < i$ 而且 $a[j] <= a[i]$ 而且 $f[i] = f[j] + 1$ ，其实就是 $dp$ 中状态转移的条件。 然后由 $j2$ 向 $i1$ 连一条容量为 $1$ 的边。 跑出来最大流就是答案。

第三问

由于 $x_1, x_n$ 可以使用多次，那么将 $S$与 $1_1$之间的边容量改为 $inf$, $1_1$与 $1_2$ 之间的边容量也改为 $inf$，如果 $f[N]=K$ 的话，就将 $N_1$和 $N_2$之间的边容量改为 $inf$， $N_2$ 和 $T$ 之间的边的容量改为 $inf$, 此时跑出的最大流为第三问答案。