Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Greatest Common Increasing Subsequence
Description You are given two sequences of integer numbers. Write a program to determine their common increasing subsequence of maximal possible length.
Sequence S _{1} , S_{2} , . . . , S_{N} of length N is called an increasing subsequence of a sequence A_{1} , A_{2} , . . . , A_{M} of length M if there exist 1 <= i_{1} < i_{2} < . . . < i_{N} <= M such that S_{j} = A_{ij} for all 1 <= j <= N , and S_{j} < S_{j+1} for all 1 <= j < N . Input Each sequence is described with M --- its length (1 <= M <= 500) and M integer numbers A _{i} (-2^{31} <= A_{i} < 2^{31} ) --- the sequence itself. Output 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. Sample Input 5 1 4 2 5 -12 4 -12 1 2 4 Sample Output 2 1 4 Source Northeastern Europe 2003, Northern Subregion |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator