自动搬运

查看原文

来自洛谷，原作者为

	winsun **

搬运于2025-08-24 21:30:40，当前版本为作者最后更新于2025-08-05 15:08:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

观察：三组相同的顺子可以变成三组刻子，因此不妨令每种顺子的数量小于 $3$。

记编号为 $i$ 的牌有 $a_i$ 张。考虑确定 $a$ 后，判定是否和牌。

令 $f(x, p, q, 0/1)$ 表示 用完编号为 $1 \sim x$ 的牌，有 $p$ 个 $(x - 1, x, x + 1)$ 的顺子，$q$ 个 $(x, x + 1, x + 2)$ 的顺子，是否使用雀头 的情况是否可能。其中 $p, q \in \{0, 1, 2\}$。

转移时讨论是否在当前位置使用雀头：

• 不使用，$f(x - 1, p, q, 0/1) \rightarrow f(x, q, (a_x - p - q) \bmod 3, 0/1)$
• 使用，$f(x - 1, p, q, 0) \rightarrow f(x, q, (a_x - p - q - 2) \bmod 3, 1)$

暴力枚举在哪里 $+1$ 可得到 $O(n^2)$ 算法。

考虑正着倒着分别 DP 一遍，然后假定在 $x$ 处听牌，枚举使用了 $p$ 个 $(x - 2, x - 1, x)$，$q$ 个 $(x, x + 1, x + 2)$，讨论雀头位于 $[1, x-1]$，$x$，$[x+1, n]$ 中哪一部分，逐一判断能否成立。时间复杂度 $O(n)$，常数较小。