最长递增子序列问题

Description

给定正整数序列 x1,x2,x3,...,xn$x_1, x_2, x_3,...,x_n$ （1）计算其最长递增子序列的长度 s。 （2）计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。 （3）如果允许在取出的序列中多次使用x1$x_1$和xn$x_n$，则从给定序列中最多可取出多少个长度为 s 的递增子序列。

Input

第 1 行有 1 个正整数 n，表示给定序列的长度。接下来的 1 行有 n 个正整数x1...xn$x_1...x_n$

Output

第 1 行是最长递增子序列的长度 s。第 2 行是可取出的长度为 s 的递增子序列个数。第 3 行是允许在取出的序列中多次使用x1$x_1$和xn$x_n$时可取出的长度为 s 的递增子序列个数。

题解

题面冠冕堂皇的说着什么最长递增子序列，数据竟给的是最长不上升子序列的，令人无语。 第一问可以用最简单的O(n)$O(n)$的动态规划求出，fi$f_i$为以xi$x_i$结束的最长递增子序列长度，记最长递增子序列长度为k。 下面考虑建图，因为每个xi$x_i$只能去一次，那么要限流，所以将每个xi$x_i$拆成两个点ai$a_i$和bi$b_i$，从ai$a_i$向bi$b_i$连一条容量为1的边，就可以保证流过xi$x_i$的流量最多为1。 然后从s点向每个fi=1$f_i=1$的ai$a_i$连一条容量为1的边，然后从每个fi=k$f_i=k$的bi$b_i$向t连一条容量为1的边。从满足{i<j,xi<xj,fi+1=fj}$/{i<j,x_i<x_j,f_i+1=f_j/}$的bi$b_i$向aj$a_j$连一条容量为1的边。这样，一条从s到t的可行流就是一个最长递增子序列，最大流即是答案。 对于第三问只需要将<a1,b1>，<an,bn>，<s,a1>$<s,a_1>$，<bn,t>$<b_n,t>$四条边的容量赋为inf$inf$，再算一遍最大流即可。 【建模分析】 上述建模方法是应用了一种分层图的思想，把图每个顶点i按照fi$f_i$的不同分为了若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出，需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数，所以最大流量就是第二问结果。第三问特殊地要求x1$x_1$和xn$x_n$可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可。