1759: 【基础】最长公共子序列(LCS)(1)
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:1
Description
给出1-n的两个排列P1和P2,求它们的最长公共子序列。
Input
第一行是一个数n;(n是5~1000之间的整数)
接下来两行,每行为n个数,为自然数1-n的一个排列(1-n的排列每行的数据都是1-n之间的数,但顺序可能不同,比如1-5的排列可以是:1 2 3 4 5,也可以是2 5 4 3 1)。
接下来两行,每行为n个数,为自然数1-n的一个排列(1-n的排列每行的数据都是1-n之间的数,但顺序可能不同,比如1-5的排列可以是:1 2 3 4 5,也可以是2 5 4 3 1)。
Output
一个整数,即最长公共子序列的长度。
Sample Input Copy
5
3 2 1 4 5
1 2 3 4 5
Sample Output Copy
3