← 返回题目列表

AtCoder · tkppc6_1_g

G. 最多两个

中文机器翻译题面 查看原题

配点 : 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

原案: 企鹅人