我们仍未知道那天所做的麻将题到底有没有「超级」。
考虑 DP，设 \(f_{i,0/1,j,k}\) 表示前 \(i-2\) 种牌都选满的情况下，无 / 有雀头，第 \(i-1\) 种牌选了 \(j\) 张，第 \(i\) 种牌选了 \(k\) 张时，这些牌能否和牌。
转移时考虑加入一个雀头 / 刻子 / 杠，再考虑顺子。
注意到边界条件是需要对 \(i \le 2\) 都预处理的，因为除了顺子以外无法从上个阶段转移到这个阶段。
网上的题解都是故意让其越界，从而投机取巧地解决此题，并没有透彻理解。
那么只需要考虑对第一种牌和第二种牌做背包，用 \(2/3/4\) 来拼即可。
不过由于我们的转移本质上也是做背包，所以说有比较简洁的处理方式：
令 \(f_{1,0,0,0}=1\)，循环时 \(i=1,\ldots,100\)，除非 \(i \ge 2\) 否则不能进行顺子转移。
那么注意到当 \(i=1\) 时已经算出了合法的状态。
之所以要对 \(i=2\) 也进行顺子转移，是因为「第 \(0\) 种牌」的张数是 \(0\)，顺子转移时只会从 \(f_{1,0,0,i}\) 转移到 \(f_{2,0,i,0}\)。
这样实际上就完成了我们的预处理。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
const int N = 1e2;
int T,n = N,a[N + 5];
int f[N + 5][2][N + 5][N + 5];
int main()
{
scanf("%d",&T);
for(;T;--T)
{
memset(f,0,sizeof f),f[1][0][0][0] = 1;
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= a[i - 1];++j)
for(register int k = 0;k <= a[i];++k)
{
k >= 2 && (f[i][1][j][k] |= f[i][0][j][k - 2]);
k >= 3 && (f[i][1][j][k] |= f[i][1][j][k - 3],f[i][0][j][k] |= f[i][0][j][k - 3]);
k >= 4 && (f[i][1][j][k] |= f[i][1][j][k - 4],f[i][0][j][k] |= f[i][0][j][k - 4]);
i >= 2 && j >= k && a[i - 2] >= k && (f[i][1][j][k] |= f[i - 1][1][a[i - 2] - k][j - k],f[i][0][j][k] |= f[i - 1][0][a[i - 2] - k][j - k]);
}
puts(f[n][1][a[n - 1]][a[n]] ? "Yes" : "No");
}
}