Home => ProblemSet => 2.12-49:最长公共子序列II
Problem1711--2.12-49:最长公共子序列II

1711: 2.12-49:最长公共子序列II

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 2
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

给出 1,2,…,n 的两个排列 P1 和 P2 ，求它们的最长公共子序列。

Input

第一行是一个数 n。
接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。

Output

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

Sample Input Copy 

5 
3 2 1 4 5
1 2 3 4 5

Sample Output Copy 

3

HINT

  • 对于 50% 的数据， n≤103；
  • 对于 100% 的数据， n≤105。

Source/Category

算法 动态规划 线性 
[ Submit ] [ Status ]