最长公共子序列（LCS）(1)

题目描述

给出 $1 \sim n$ 的两个排列 $P_1$ 和 $P_2$，求它们的最长公共子序列的长度。

输入格式

第一行是一个数 $n$；（$n$ 是 $5 \sim 1000$ 之间的整数）

接下来两行，每行为 $n$ 个数，为自然数 $1 \sim n$ 的一个排列。

输出格式

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

样例输入 1

5
3 2 1 4 5
1 2 3 4 5

样例输出 1

3

样例解释 1

两个序列的公共子序列最长可以取到 3 个，例如 $1, 4, 5$（在 $P_1$ 里是第 3、4、5 个，在 $P_2$ 里是第 1、4、5 个）。

样例输入 2

6
1 2 3 4 5 6
1 2 3 4 5 6

样例输出 2

6

样例输入 3

4
4 3 2 1
1 2 3 4

样例输出 3

1

样例输入 4

7
2 1 4 3 6 5 7
1 2 3 4 5 6 7

样例输出 4

4

数据范围

• $5 \le n \le 1000$
• 两行各是 $1 \sim n$ 的一个排列，每行的 $n$ 个数互不相同