|Online Judge||Problem Set||Authors||Online Contests||User|
Greatest Common Increasing Subsequence
You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length.
Sequence S1 , S2 , . . . , SN of length N is called an increasing subsequence of a sequence A1 , A2 , . . . , AM of length M if there exist 1 <= i1 < i2 < . . . < iN <= M such that Sj = Aij for all 1 <= j <= N , and Sj < Sj+1 for all 1 <= j < N .
Each sequence is described with M --- its length (1 <= M <= 500) and M integer numbers Ai (-231 <= Ai < 231 ) --- the sequence itself.
On the first line of the output file print L --- the length of the greatest common increasing subsequence of both sequences. On the second line print the subsequence itself. If there are several possible answers, output any of them.
5 1 4 2 5 -12 4 -12 1 2 4
2 1 4
Northeastern Europe 2003, Northern Subregion
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator