Problem1821--【基础】最长公共子序列(LCS)(1)

1821: 【基础】最长公共子序列(LCS)(1)

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 1
[Submit] [Status] [Web Board] [Creator:][下载测试数据]

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）。

Output

一个整数，即最长公共子序列的长度。

Sample Input

5 
3 2 1 4 5
1 2 3 4 5

Sample Output

3

Source/Category

动态规划 

[Submit] [Status]