最长公共上升子序列

成绩 100 开启时间 2016年05月30日 星期一 18:30
折扣 0.8 折扣时间 2016年05月30日 星期一 18:30
允许迟交 是 关闭时间 2016年05月30日 星期一 18:30
输入文件 LCIS.in 输出文件 LCIS.out

【题目描述】最长公共上升子序列（LCIS.cpp/c/pas）POJ 2127

　　研究发现，大猩猩的基因序列和人的基因序列只有1.3%的区别，更进一步，不仅仅离人最近的大猩猩和人的基因序列高度近似，就连以打洞为生的老鼠和人的基因序列也有高达95%的相同序列。于是有魔法师提出一个大胆设想，即改变人类的某些特定基因以期产生超级人类。

    现在，他们要做的第一步是将两种不同生物的基因序列转换成两个整数序列，并试图确定他们的最大公共上升子序列的长度，例如有A序列为4 3 2 1 7 8 9，B序列为7 8 9 4 3 2 1，其最长公共子序列是4 3 2 1，而最长公共递增子序列应该是 7 8 9。

【输入格式】

输入每个序列由M个整数组成(1 ≤ M ≤500)，M个整数范围在(－231 ≤Bi < 231)之间。

【输出格式】

第一行输出最长公共上升子序列长度L，第二行输出该子序列，如果该序列有多个答案，输出任意一个即可。

　　【输入样例】

5

1 4 2 5 -12

4

-12 1 2 4

【输出样例】

　　2

　　1 4 (注：结果非唯一)

　　【时间限制】

　　5秒