AT_abc185_e [ABC185E] Sequence Matching

题目描述

有一个长度为 $N$ 的整数序列 $A$，以及一个长度为 $M$ 的整数序列 $B$。
高桥君可以从 $A$ 中删除若干元素，并将剩下的元素按原顺序连接，得到一个新序列 $A'$（可以一个都不删，也可以全部删掉）。
对于 $B$ 也同样，可以删除若干元素，剩下的元素按原顺序连接，得到新序列 $B'$（同样可以一个都不删，也可以全部删掉）。
此时，需要选择一种删除方式，使得 $|A'| = |B'|$（对于序列 $s$，$|s|$ 表示 $s$ 的长度）。
设从 $A$ 和 $B$ 中总共删除的元素个数为 $x$，并且 $1 \leq i \leq |A'|$ 且 ${A'}_i \neq {B'}_i$ 的整数 $i$ 的个数为 $y$，请你求出 $x + y$ 的最小可能值。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$A_1\ A_2\ A_3\ \dots\ A_N$
$B_1\ B_2\ B_3\ \dots\ B_M$

输出格式

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

输入输出样例 #1

输入 #1

4 3
1 2 1 3
1 3 1

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

3

输入输出样例 #3

输入 #3

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

输出 #3

5

说明/提示

限制条件

• $1 \leq N, M \leq 1000$
• $1 \leq A_i, B_i \leq 10^9$
• 输入均为整数

样例解释 1

从 $A$ 中删除 $A_4$ 得到 $A'$，从 $B$ 中不删除任何元素得到 $B'$，此时 $x = 1$。
并且此时满足 $1 \leq i \leq |A'|$ 且 ${A'}_i \neq {B'}_i$ 的 $i$ 只有 $2$ 这一个，所以 $y = 1$。因此 $x + y = 2$，这是最小值。

样例解释 2

从 $A$ 中不删除任何元素，从 $B$ 中删除 $B_4$ 和 $B_6$ 这两个元素，则 $x = 2, y = 1$，所以 $x + y = 3$，这是最小值。

样例解释 3

允许 $A$ 和 $B$ 都不删除任何元素。

由 ChatGPT 4.1 翻译