P16883 [GKS 2022 #D] Touchbar Typing

Crowdsource 应用中的滑动输入任务使用了一种新的 Google 键盘，通过在不抬起手指的情况下在按键上滑动来输入单词，如下面的动画所示。 :::align{center}  ::: 为了使滑动输入任务更具挑战性，我们使用的不是普通键盘，而是一个特殊的线性键盘 $K$，所有按键排成一行。 假设你想输入一个长度为 $N$ 的单词 $S$。线性键盘 $K$ 有 $M$ 个按键。保证键盘上的按键覆盖了 $S$ 中的所有字符。但是，有些按键可能是重复的。换句话说，对于 $S$ 中的每个字符，在 $K$ 中存在一个或多个按键映射到该字符。注意，所有字符和按键都用整数表示。 你可以将手指放在任意一个按键上开始。将手指从一个按键移动到相邻按键需要 $1$ 秒。由于是滑动输入，不需要按动按键。如果手指当前位于索引 $i$ 的按键（该按键字符为 $K_i$），并且我们想输入字符 $K_j$（即索引 $j$ 处的字符），我们将手指从按键 $i$ 滑动到按键 $j$，这需要 $|j - i|$ 秒。如果你的手指在按键 $x$ 上，你可以瞬间多次输入字符 $K_x$。你需要逐个字符地输入字符串 $S$。形式化地说，对于每个 $1 \le i \le N-1$，你必须在输入 $S_{i+1}$ 之前先输入 $S_i$。 例如，假设单词 $S$ 的字符为：$1, 2, 2, 3, 4$。你可以先让手指放在键盘上字符为 $1$ 的按键（位于索引 $i$）上。然后，将手指滑动到字符为 $2$ 的按键（位于索引 $j$）上。这将花费 $|j - i|$ 秒。为了在字符串 $S$ 中连续输入两个 $2$，你可以不花额外时间完成，因为 $|j - j| = 0$ 秒。然后你可以继续滑动手指以顺序输入单词 $S$ 中的其余字符。 请计算出输入该单词所需的最小时间。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$：单词 $S$ 的长度。 每个测试用例的第二行包含 $N$ 个整数：其中 $S_i$ 表示第 $i$ 个位置上的字符。 每个测试用例的第三行包含一个整数 $M$：键盘 $K$ 的长度。 每个测试用例的第四行包含 $M$ 个整数：其中 $K_i$ 表示第 $i$ 个按键上的字符。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是在键盘 $K$ 上输入 $S$ 所需的最小时间。

在样例 #1 中，我们可以按照以下步骤以最短时间输入字符串 $S$。 - 将手指放在字符为 $1$ 的按键 $K_1$ 上。现在我们已经输入了字符串 $S$ 的第一个字符。 - 为了输入字符串 $S$ 的第二个字符 $2$，将手指滑动到按键 $K_2$。从索引 $1$ 滑动到索引 $2$ 需要额外 $|2 - 1| = 1$ 秒。 - 为了输入字符串 $S$ 的第三个字符 $3$，将手指滑动到按键 $K_3$。从索引 $2$ 滑动到索引 $3$ 需要额外 $|3 - 2| = 1$ 秒。 - 为了输入字符串 $S$ 的第四个字符 $2$，将手指滑动到按键 $K_2$。从索引 $3$ 滑动到索引 $2$ 需要额外 $|2 - 3| = 1$ 秒。 - 为了输入字符串 $S$ 的第五个字符 $1$，将手指滑动到按键 $K_1$。从索引 $2$ 滑动到索引 $1$ 需要额外 $|1 - 2| = 1$ 秒。 - 我们总共用了 $4$ 秒输入完字符串 $S$ 的所有字符。 在样例 #2 中，我们可以按照以下步骤以最短时间输入字符串 $S$。 - 将手指放在字符为 $1$ 的按键 $K_2$ 上。现在我们已经输入了字符串 $S$ 的第一个字符。 - 由于手指在按键 $K_2$ 上，我们可以无额外时间地多次输入字符 $1$。因此，我们可以输入字符串 $S$ 的第二和第三个字符。 - 我们总共用了 $0$ 秒输入完字符串 $S$ 的所有字符。 ### 限制条件 $1 \le T \le 100$。 $S$ 中的每个字符至少出现在 $K$ 中一次。 $1 \le K_i \le 2500$。 $1 \le S_i \le 2500$。 **测试集 1** $1 \le N \le 100$。 $1 \le M \le 100$。 保证键盘 $K$ 中没有重复的按键。 **测试集 2** $1 \le N \le 100$。 $1 \le M \le 100$。 **测试集 3** $1 \le N \le 2500$。 $1 \le M \le 2500$。 翻译由 DeepSeek V4 Pro 完成