BZOJ 1028 「JSOI2007」麻将

最近麻将题写上瘾了……（

显然地考虑枚举听的那张牌，然后判定是否可以和牌。
考虑 DP，设 fi,0/1,j,k 表示考虑了前 i 种牌，无 / 有雀头，除去做面子的牌还有 j 组 (i−1,i)，k 张 i 的情况下最多可以做多少面子。
则枚举第 i 种牌预留多少张，即可转移。
每次转移的时候考虑拿 2 张出来组雀头就行了。

最后因为刚好是 3m+2 张，所以肯定不会有多的 (n−1,n) 或单独的 n，故只有 fn,1,0,0=m 时才算和牌。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 400;
const int M = 1e3;
int n,m,a[N + 5],flag;
int f[N + 5][2][3][3];
inline int dp()
{
    memset(f,-0x3f,sizeof f)，f[0][0][0][0] = 0;
    for(register int i = 1;i <= n;++i)
        for(register int j = 0;j < 3;++j)
            for(register int k = 0;k < 3;++k)
            {
                for(register int l = 0;l < 3 && j + k + l <= a[i];++l)
                    f[i][0][k][l] = max(f[i][0][k][l],f[i - 1][0][j][k] + j + (a[i] - j - k - l) / 3),
                    f[i][1][k][l] = max(f[i][1][k][l],f[i - 1][1][j][k] + j + (a[i] - j - k - l) / 3);
                if(a[i] >= 2)
                    for(register int l = 0;l < 3 && j + k + l <= a[i] - 2;++l)
                        f[i][1][k][l] = max(f[i][1][k][l],f[i - 1][0][j][k] + j + (a[i] - 2 - j - k - l) / 3);
            }
    return f[n][1][0][0] >= m;
}
int main()
{
    scanf("%d%d",&n,&m);
    int x;
    for(register int i = 1;i <= 3 * m + 1;++i)
        scanf("%d",&x),++a[x];
    for(register int i = 1;i <= n;++i)
        ++a[i],dp() && (flag |= 1,printf("%d ",i)),--a[i];
    !flag && puts("NO");
}