【问题分析】

第一问时LIS，动态规划求解，第二问和第三问用网络最大流解决。

【建模方法】

首先动态规划求出F[i]，表示以第i位为开头的最长上升序列的长度，求出最长上升序列长度K。

1、把序列每位i拆成两个点<i.a>和<i.b>，从<i.a>到<i.b>连接一条容量为1的有向边。 2、建立附加源S和汇T，如果序列第i位有F[i]=K，从S到<i.a>连接一条容量为1的有向边。 3、如果F[i]=1，从<i.b>到T连接一条容量为1的有向边。 4、如果j>i且A[i] < A[j]且F[j]+1=F[i]，从<i.b>到<j.a>连接一条容量为1的有向边。

求网络最大流，就是第二问的结果。把边(<1.a>,<1.b>)(<N.a>,<N.b>)(S,<1.a>)(<N.b>,T)这四条边的容量修改为无穷大，再求一次网络最大流，就是第三问结果。

【建模分析】

上述建模方法是应用了一种分层图的思想，把图每个顶点i按照F[i]的不同分为了若干层，这样图中从S出发到T的任何一条路径都是一个满足条件的最长上升子序列。由于序列中每个点要不可重复地取出，需要把每个点拆分成两个点。单位网络的最大流就是增广路的条数，所以最大流量就是第二问结果。第三问特殊地要求x1和xn可以重复使用，只需取消这两个点相关边的流量限制，求网络最大流即可。

最长递增子序列问题
问题描述: 给定正整数序列x1,...,xn 。 (1)计算其最长递增子序列的长度 s。 (2)计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。 (3)如果允许在取出的序列中多次使用 x1 和 xn,则从给定序列中最多可取出多少个长度为 s 的递增子序列。
编程任务:
设计有效算法完成(1)(2)(3)提出的计算任务。 ́数据输入: 由文件 input.txt 提供输入数据。文件第 1 行有 1 个正整数 n,表示给定序列的长度。接
下来的 1 行有 n 个正整数 x1 ,.., xn 。
结果输出:
程序运行结束时,将任务(1)(2)(3)的解答输出到文件 output.txt 中。第 1 行是最长 递增子序列的长度 s。第 2 行是可取出的长度为 s 的递增子序列个数。第 3 行是允许在取出 的序列中多次使用 x1 和 xn 时可取出的长度为 s 的递增子序列个数。
输入文件示例
input.txt
4
3 6 2 5
输出文件示例
output.txt
2
2
3

上次修改时间 2017-02-03