Sequence Matching

题目描述

我们有一个长度为 $N$ 的整数序列 $A$ 和一个长度为 $M$ 的整数序列 $B$。
Takahashi 将通过从 $A$ 中删除若干元素（可能为零个或全部）并将剩下的元素连接起来构造一个新序列 $A'$。
类似地，他将通过从 $B$ 中删除若干元素（可能为零个或全部）并将剩下的元素连接起来构造另一个新序列 $B'$。
这里，他会删除元素使得 $|A'| = |B'|$。（对于序列 $s$，$|s|$ 表示其长度。）
令 $x$ 为从 $A$ 和 $B$ 中删除的元素的总数，令 $y$ 为满足 $1 \le i \le |A'|$ 且 ${A'}_i \neq {B'}_i$ 的整数 $i$ 的个数。输出 $x + y$ 的最小可能值。

输入格式

输入从标准输入按如下格式给出： $N$ $M$ $A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_N$ $B_1 \hspace{7pt} B_2 \hspace{7pt} B_3 \hspace{5pt} \dots \hspace{5pt} B_M$

输出格式

输出 $x + y$ 的最小可能值。

4 3
1 2 1 3
1 3 1

2

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

3

5 5
1 1 1 1 1
2 2 2 2 2

5

提示

$1 \le N, M \le 1000$ $1 \le A_i, B_i \le 10^9$ 输入中的所有值均为整数。如果我们通过从 $A$ 中删除 $A_4$ 来构造 $A'$，并且不从 $B$ 中删除任何元素来构造 $B'$，则 $x$ 为 $1$。
在这里，满足 $1 \le i \le |A'|$ 且 ${A'}_i \neq {B'}_i$ 的整数 $i$ 只有一个：$i = 2$，因此 $y$ 为 $1$，且 $x + y$ 为 $2$，这是最小可能值。
如果我们不从 $A$ 中删除任何元素而从 $B$ 中删除 $B_4, B_6$，则有 $x = 2, y = 1$，且 $x + y = 3$，这是最小可能值。
允许对 $A$ 和 $B$ 都不删除任何元素。

标签: AtCoder|abc185E

来源

AtCoder|abc185E