题解：P1820 麻将 加强加强版

winsun · 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)，常数较小。