题目
给定点数为1~K的麻将牌各4张(这4张完全相同),问有多少种方案,从中选出一个M张牌组成的集合,能够和牌。“和牌”指:其中有两张完全相同的将牌,其他牌可以被三三分组,每组要么是“n-1 n n+1”型,要么是“n n n”型。注意:集合相同而和法不同仅算一次。
题解
我们考虑这样一个命题:如果给定一个集合,能否和牌。这是一个很简单的DP:大致是:f[i][n2][n1][p]={0,1},其中i是到了点数为i的,n2是以i-2开始的连牌组数,n1以i-1的连牌组数,p是是否有将牌。对于点数为i的牌,枚举是否从中选取将牌,尔后贪心转移即可。
我们可以发现:这样的(n2,n1,p)的状态只有3*3*2=18个(n2,n1<=2,p<=1)。换言之:用一个长度为18的01数即可表示出某个状态的所有DP情况。我们设这个状态是s,那么对于原先的题目,如果开一个DP数组:F[i][s],表示到了点数为i的牌,到达DP情况为s的方案数。不妨把这个s想象成某种“虚拟机”,F[i][s]就是到达这个“虚拟机”的方案数。在最后,如果“虚拟机”中代表结束的状态为1,就代表能够和牌。
但是还有个问题:2^18显然太大,我们不能都存下来。怎么办呢?实际上我们可以发现,合法的“虚拟机”个数很少(仅有68)个,先BFS把它们都找出来,哈希一下编个号即可。
这个做法是队友@KuribohG告诉我的,当时惊为天人,因为这个算法背后的思想十分深刻。它在一个DP的基础上进行了更高一层的抽象,实质上是在下标里储存了全部的DP信息,即一个“虚拟机”。
代码
#include
#include
#include
#include
#include