0%

LOJ3042 「ZJOI2019」麻将

参考 cz_xuyixuan的blog

Sol

把原问题转化成 $\sum_{i=0}^\infty P(S_i 不存在一个子集能胡)$ 。要算这个玩意则需要对每个 $i$ ,求出大小为 $i$ 且加上初始的牌之后不存在胡子集的子集的数量。

怎样判断一副牌能不能胡:

  1. 如果有不少于 $7$ 种牌,每种牌的数量都不少于 $2$ ,就能胡;
  2. 设 $f_{i,x,y,0/1}$ 表示考虑了前 $i$ 种牌,从 $i-1$ 开始的 $(a,a+1,a+2)$ 型的面子有 $x$ 个,从 $i$ 开始的 $(a,a+1,a+2)$ 型的面子有 $y$ 个,前 $i$ 种牌是否凑出过对子,这种情况下能够得到的面子数量的最大值(不包括从 $i,i-1$ 开始的 $(a,a+1,a+2)$ 型面子)。由于三个 $(a,a+1,a+2)$ 型的面子可以转化成三个 $(a,a,a)$ 型的面子,所以 $0\le x,y < 3$ 。如果 $f_{n,x,y,1} \ge 4$ ,就能胡;

把 $f_i$ 每个位置的取值、以及能凑出对子的牌的数量,作为 dp 的状态进行 dp 即可。搜索发现状态数不超过 3227 。

Code

link