Codeforces 1110D Jongmah

（是的又是个麻将题）

首先我们把牌面上为 x 的牌称为第 x 种牌。
考虑 DP，设 fi,j,k 表示前 i 种牌，除了面子以外留出了 j 组 (i−1,i) 和 k 张 i。
注意到 0≤j,k<3，否则可以算成刻子。
则转移时枚举预留多少张牌即可，剩下的牌都贪心地组成面子。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6;
int n,m,a[N + 5];
int f[N + 5][3][3],ans = -0x3f3f3f3f;
int main()
{
    scanf("%d%d",&n,&m);
    int x;
    for(register int i = 1;i <= n;++i)
        scanf("%d",&x),++a[x];
    memset(f,-0x3f,sizeof f),f[0][0][0] = 0;
    for(register int i = 1;i <= m;++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][k][l] = max(f[i][k][l],f[i - 1][j][k] + j + (a[i] - j - k - l) / 3);
    for(register int i = 0;i < 3;++i)
        for(register int j = 0;j < 3;++j)
            ans = max(ans,f[m][i][j]);
    printf("%d\n",ans);
}