题解：P2593 [ZJOI2006] 超级麻将

补充为什么能够想到这样的状态设计、以及这样的设计为什么是对的。

设计一个一百维的状态显然不现实，而且也不必要。

和牌是若干句话（面子）和一对相同的牌（将牌，也可以叫雀头），第一步显然可以尝试枚举将牌。

问题转化成剩下的牌判断能不能组成若干句话。

假设只能做碰碰胡（对对和），也就是全部都是刻子（三张相同牌）和杠（四张相同牌），那么判断方式非常简单，依次判断每张牌的数量能不能写成 $3n+4m$ 的形式即可。

不过，不能做碰碰胡的情况很多，比如五张三万，只用刻子和杠子，肯定会剩下一张或者两张三万用不掉。

这个时候就可以引入顺子（三张连续牌）了，顺子在本题的意义就是消耗掉这些不能形成刻子和杠子的剩余牌。

考虑一张三万，能够用上它的顺子只有三种：一二三、二三四、三四五。

所以如果在检查的时候，已经检查到六万及往后的牌，而前面的三万没用完，不用想，肯定和不了了，因为这张三万一定没有机会用上了。

但反过来，用数学归纳的思想，如果前面的检查都成立，那么检查到 $i$ 的时候，需要关心的只是 $i-1$ 和 $i-2$ 两张牌的数量。再往前的必定都是零，对现在没有影响。

这就提供了优化状态设计的思路。核心在于，顺子的长度只有三，意味着每个 $i$ 的有效窗口期也最多是三个。

这类优化掉“不再关心”的状态的思想，其实在滚动数组优化背包 dp 里也有体现。

别的题解有的是让 $i$ 去关心 $i$ 和 $i-1$，或者 $i$ 和 $i+1$，也可以，核心都是在只关心附近的牌。

据此可以写出 dp。

注意，“有刻子就尽量拆出刻子”这种太过简单的贪心是不对的。

反例：五五六六七七七八八八九九九九，一种拆法是五六七、五六七、七八九、九九九、一对八万做将。直接把三个七万和三个八万拆出来是和不了的。