配点 : 500 点
問題文
长度 小于或等于 N 整数序列 给出 A,以及长度 M 整数序列 给出 B 。 对于
A, B 的最长公共子序列(LCS)的长度。
另外,在这个问题中保证以下内容。
- 任意整数 关于 x , 当我输入A_i=x 纳鲁 如果 i 最多是 2 仅存在一个。
最长公共子序列是什么?
是 小于或等于 2 数列 x, y 的最长公共子序列是,x 的子序列,并且 y 也是 的子序列的数列。 z 指的是其中长度最长的那个。
这里是某个数列 p 的子序列是 指由p 减去 0 个以上的元素中取出,并按原顺序排列的序列。
制約
- 1 \leq N,M \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9\ (1 \leq i \leq N)
- 1 \leq B_i \leq 10^9\ (1 \leq i \leq M)
- 任意整数 关于 x , 当我输入A_i=x 纳鲁 如果 i 最多是 2 只存在到...为止
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N M A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
出力
A 和 按字典顺序比较 B 的最长公共子序列的长度。 这是
入力例 1
3 3 1 2 2 2 1 2
出力例 1
2
(1,2)或 (2,2) 是 在 A 和 按字典顺序比较 B 的最长公共子序列。
入力例 2
2 3 1 3 2 4 6
出力例 2
0
这样,A 和 按字典顺序比较 B 的最长公共子序列也可能为空。
入力例 3
6 5 3 1 5 3 1 4 10 4 9 10 2
出力例 3
1
原案: 企鹅人