题目大意

给定已经打出的牌和宝牌列表，求在所有尚未打出的牌中，能够组成的和牌型手牌中「达成分数」的最大值。

和牌型包括：

• 普通和牌（$3 \times 4 + 2$）
• 七对子
• 国士无双（十三幺）
• 含杠子的和牌（$15$-$18$ 张牌）

达成分数计算：

• 基本分 = $\prod$ 选择剩余牌组成手牌的组合数
• 乘上 $2^{\text{宝牌数}}$
• 七对子额外乘 $7$，国士无双额外乘 $13$

问题分析

本题是一个麻将牌型枚举 + 组合计数问题，难点在于：

1. 状态空间巨大：$34$ 种牌，每种 $0$-$4$ 张，状态数为 $5^{34}$，不可直接枚举
2. 多种和牌型：需要分别处理普通型、七对子、国士无双
3. 组合数学计算：对于每种可能的手牌，要计算其达成方案数

解题思路

1. 数据预处理

• 将 $34$ 种牌编号（$0$-$33$）
• 统计每种牌的剩余数量：$4 - \text{已打出数量}$
• 标记哪些牌是宝牌

2. 分别计算三种和牌型的最高分

(1) 国士无双（十三幺）

• 条件：包含 $13$ 种幺九字牌各至少 $1$ 张，且总牌数 $14$ 张
• 枚举：哪张牌多 $1$ 张作为雀头
• 分数计算：
  • 对于 $13$ 种牌，选择至少 $1$ 张：$\prod \binom{\text{remain}_i}{1}$
  • 对于多 $1$ 张的那张牌：乘 $\binom{\text{remain}_j-1}{1}$
  • 乘 $2^{\text{宝牌数}}$，再乘 $13$

(2) 七对子

• 条件：$7$ 个不同的对子
• 枚举：选择 $7$ 种牌，每种牌取 $2$ 张
• 分数计算：
  • $\prod \binom{\text{remain}_i}{2}$（选择 $7$ 种牌）
  • 乘 $2^{\text{宝牌数}}$，再乘 $7$

(3) 普通和牌（$3 \times 4 + 2$）

这是最复杂的部分，采用DP搜索：

DP状态设计：

• 按万、筒、索、字牌的顺序处理
• 状态：$f[i][j][k][a][b][c]$ 表示：
  • 处理到第 $i$ 种牌
  • 已有 $j$ 个面子
  • 已有 $k$ 个杠子
  • 前面残留 $a$ 张牌需要顺子
  • 前面残留 $b$ 张牌需要顺子
  • 当前是否有雀头（$0/1$）

状态转移： 对于第 $i$ 种牌，枚举取 $t$ 张（$0 \le t \le \text{remain}_i$）：

• 组成刻子：$t \ge 3$
• 组成杠子：$t = 4$
• 组成雀头：$t \ge 2$ 且之前无雀头
• 组成顺子：数字牌可向前面的残留牌组成顺子

分数计算： 当 $j = 4$（$4$ 面子）且有雀头时，计算当前方案的分数：

• 组合数：$\prod \binom{\text{remain}_i}{t_i}$
• 宝牌倍率：$2^{\sum \text{宝牌数}}$

3. 含杠子的和牌

通过调整DP状态中的面子数和杠子数来处理：

• $15$ 张：$3$ 面子 + $1$ 杠子 + $1$ 雀头
• $16$ 张：$2$ 面子 + $2$ 杠子 + $1$ 雀头
• $17$ 张：$1$ 面子 + $3$ 杠子 + $1$ 雀头
• $18$ 张：$0$ 面子 + $4$ 杠子 + $1$ 雀头

算法优化

1. 状态剪枝：面子数 $>4$、杠子数 $>4$、残留牌 $>2$ 的状态直接舍弃
2. 牌型分组：万、筒、索、字牌分开处理，字牌不能组成顺子
3. 记忆化搜索：对每个花色进行DP，减少状态数
4. 组合数预处理：预计算所有 $\binom{n}{k}$

复杂度分析

• 国士无双：$O(13)$ 枚举
• 七对子：$O(\binom{34}{7})$ 但可用堆优化到 $O(34 \log 7)$
• 普通和牌：DP状态数约 $34 \times 5^5 \times 2 \approx 10^5$，可接受

代码实现要点

// 伪代码框架
vector<int> remain(34, 4);  // 每种牌剩余数量
vector<bool> dora(34, false); // 宝牌标记

// 1. 读入数据，更新remain和dora

// 2. 计算国士无双分数
ans = max(ans, kokushi());

// 3. 计算七对子分数  
ans = max(ans, seven_pairs());

// 4. 计算普通和牌分数
DP状态初始化
for 每种花色:
   进行DP转移
ans = max(ans, 普通和牌最高分)

// 5. 输出答案

总结

本题综合了状态DP、组合数学、麻将规则等多种知识点，需要：

1. 深入理解麻将的各种和牌型
2. 设计合适的状态表示和转移方程
3. 高效处理组合计数和宝牌倍率

通过分别处理三种和牌型，并利用DP搜索普通和牌，可以在合理时间内求出最高达成分数。