BZOJ 1860 「ZJOI2006」超级麻将

我们仍未知道那天所做的麻将题到底有没有「超级」。

考虑 DP，设 fi,0/1,j,k 表示前 i−2 种牌都选满的情况下，无 / 有雀头，第 i−1 种牌选了 j 张，第 i 种牌选了 k 张时，这些牌能否和牌。

转移时考虑加入一个雀头 / 刻子 / 杠，再考虑顺子。
注意到边界条件是需要对 i≤2 都预处理的，因为除了顺子以外无法从上个阶段转移到这个阶段。
网上的题解都是故意让其越界，从而投机取巧地解决此题，并没有透彻理解。

那么只需要考虑对第一种牌和第二种牌做背包，用 2/3/4 来拼即可。
不过由于我们的转移本质上也是做背包，所以说有比较简洁的处理方式：
令 f1,0,0,0=1，循环时 i=1,…,100，除非 i≥2 否则不能进行顺子转移。
那么注意到当 i=1 时已经算出了合法的状态。
之所以要对 i=2 也进行顺子转移，是因为「第 0 种牌」的张数是 0，顺子转移时只会从 f1,0,0,i 转移到 f2,0,i,0。
这样实际上就完成了我们的预处理。

代码：

#include <cstdio>
#include <cstring>
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");
    }
}