本文共 5233 字，大约阅读时间需要 17 分钟。

题目

题目描述

打麻将你得知道的事情：和

——有哪些牌？

• 普通的：万子、筒子、条子。
• 新鲜的：东南西北；红中、白板、绿发。

——牌的组合？

• 刻子：三张一样的牌。
• 顺子：三张连续的牌。顺子、刻子统称为“面子”。
• 对子：两张一样的牌。在和牌组合中也叫做“将”。
• 杠子：四张一样的牌。

——和牌的组合？

• 过小份：$4\times$面子$+1\times$将。共$14$张。
• 七对：$7\times$对子。共$14$张。对子是不同的。七对的优秀度会额外扩大为原来的$7$倍。
• 国士无双：仅包含数字为一或九的筒、万、条，加上东南西北中白发，每种至少一张。共$14$张。优秀度扩大为原来的$13$倍。
• 杠一次，剩下的组成$3\times$面子$+1\times$将。共$15$张。
• 杠两次，剩下的组成$2\times$面子$+1\times$将。共$16$张。
• 杠三次，剩下的组成$1\times$面子$+1\times$将。共$17$张。
• 杠四次，剩下的组成$1\times$将。共$18$张。

输入输出格式

数据范围与约定

思路

龟速的$\text{DP}$

$dp[i][j][k][l][r]$表示有$i$个杠、$j$个对、$k$个面子，最大优秀度。倒数第二个选了$l$个；倒数第一个选了$r$个。并且都“空闲”着——没有被统计为面子什么的。显然有$i\le 4,j\le 7,k\le 4,l\le 4,r\le 4$.

国士无双单独考虑。

然后我就$\text{TLE}$飞了……在某谷上只能过$20\text{pts}$的数据。

高效的$\text{DP}$

我们有很多优化可以打——

• 七对单独做。发现$j$之所以要开到$7$，全是七对在搞鬼。如果我模仿国士无双的处理方法，我就可以把$j$开成$0/1$.
• 杠子不需要。发现杠子的贡献无非是$2C_4^4=2$，而刻子的贡献是$C_4^3=4$，所以根本不会用杠子的。也就是说，其实只有七对、国士无双、四面一将需要被考虑。于是我们又降了一维。
• 如果你用$dp[i,j,k,l,r]$去更新别人，那么$dp[i,j,k,l,r]=0$时就不用更新了。

这就是全部优化了。但这些就足以助你通过此题！

代码

#include 
   
    #include 
    
     #include 
     
      #include