P14732 [ICPC 2022 Seoul R] Shuffle Game

洗牌游戏是庄家和玩家之间的一种简单纸牌游戏。初始时，庄家和玩家都得到一副相同的 $n$ 张牌。牌堆中的每张牌由四种花色之一（$C$, $D$, $H$ 或 $S$）和 13 种点数之一（$2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $A$, $J$, $K$ 或 $Q$）组成。因此，共有 $52$ 种不同类型的牌，且相同的牌可以在牌堆中出现多张。将牌分发给庄家和玩家后，庄家首先从自己得到的牌堆中通过任意洗牌方法创建自己的牌堆 $X$，并将其展示给玩家。之后，玩家通过以下步骤创建牌堆 $Y$：初始时 $Y$ 为空。 **步骤 1.** 从玩家得到的牌堆中创建两个牌堆 $P1$ 和 $P2$。$P1$ 和 $P2$ 中的牌数可以不同。 **步骤 2.** 交错合并 $P1$ 和 $P2$。即，将 $P1$ 或 $P2$ 底部的牌移至 $Y$ 的当前顶部，直到 $P1$ 和 $P2$ 中都没有牌为止。注意，玩家不需要交替地将 $P1$ 和 $P2$ 中的牌移至 $Y$。此外，由于庄家和玩家都从相同的 $n$ 张牌堆创建自己的牌堆，$Y$ 总是由与 $X$ 相同的牌组成。 我们将一个牌堆的序列定义为从底部到顶部牌的顺序。那么玩家的得分定义为序列 $X$ 和 $Y$ 之间的最长公共子序列的长度。例如，假设庄家和玩家都得到 $n = 5$ 张牌的牌堆 $(C2, CJ, D5, HA, S7)$（这里，我们用其序列表示牌堆）。然后庄家创建牌堆 $X = (CJ, D5, HA, C2, S7)$ 并将其展示给玩家。之后，玩家通过以下方式创建自己的牌堆：(i) 从给定牌堆中创建两个牌堆 $P1 = (D5, HA)$ 和 $P2 = (CJ, S7, C2)$，以及 (ii) 通过交错合并 $P1$ 和 $P2$ 创建 $Y = (D5, CJ, S7, HA, C2)$。在此示例中，玩家的得分为 $3$，因为 $(CJ, HA, C2)$ 是 $X$ 和 $Y$ 序列之间的最长公共子序列。现在，在完成步骤 1 后，玩家希望在应用步骤 2 后知道自己可能获得的最大得分。例如，在前一个示例中，$X$ 和 $Y$ 的最大可能得分为 $4$，因为可以从 $P1$ 和 $P2$ 创建 $Y$ 为 $(CJ, D5, HA, S7, C2)$。 给定 $n$、$X$、$P1$ 和 $P2$，请编写一个程序计算玩家可能获得的最大得分。

你的程序需要从标准输入读取数据。输入的第一行包含三个正整数 $n$、$p$ 和 $q$ ($3 \leq n \leq 500$, $p + q = n$)，其中 $n$ 是初始牌堆中的牌数，$p$ 和 $q$ 分别是 $P1$ 和 $P2$ 中的牌数。接下来的三行中，分别给出庄家的牌堆 $X$（包含 $n$ 张牌），以及玩家的两个牌堆 $P1$ 和 $P2$（分别包含 $p$ 和 $q$ 张牌）。$X$、$P1$ 和 $P2$ 中的每张牌由其花色（大写字母 $C$、$D$、$H$ 或 $S$）和点数（$2$、$3$、$4$、$5$、$6$、$7$、$8$、$9$、$10$，或大写字母 $A$、$J$、$K$、$Q$）表示。同一行中的牌按对应牌堆从底部到顶部的顺序排列。

你的程序需要向标准输出写入数据。输出恰好一行。该行应包含玩家在应用步骤 2 后，基于 $X$、$P1$ 和 $P2$ 可能获得的最大得分。

翻译由 DeepSeek V3 完成