2466: 最长公共子序列2

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:7 通过:5

题目描述

给出两个长度为 n 的整数序列,求它们的最长公共子序列(LCS)的长度,保证第一个序列中所有元素都不重复。

注意:

  • 第一个序列中的所有元素均不重复。
  • 第二个序列中可能有重复元素。
  • 一个序列中的某些元素可能不在另一个序列中出现。

输入格式

第一行包含一个整数 n。

接下来两行,每行包含 n 个整数,表示一个整数序列。

输出格式

输出一个整数,表示最长公共子序列的长度。

数据范围

1≤n≤106
序列内元素取值范围 [1,106]

输入样例1:

5
1 2 3 4 5
1 2 3 4 5

输出样例1:

5

输入样例2:

5
1 2 3 5 4
1 2 3 4 5

输出样例2:

4


输入样例 复制

5
1 2 3 4 5
1 2 3 4 5

输出样例 复制

5