题目概述

有 $m$ 种牌共 $n$ 张，求最多组成多少面子（即顺子 $i,i+1,i+2$ 或者刻子 $i,i,i$ ）。

解题报告

题目名称是将麻可还行……CF泄露天机？

首先有暴力DP：$f_{i,j,k}$ 表示 $i-1$ 用了 $j$ 张，$i$ 用了 $k$ 张的最多面子数。

但是这样存不下……我们发现连续的 $3$ 组顺子其实可以当成 $3$ 组刻子，所以可以定义 $f_{i,j,k}$ 表示以 $i-1$ 结尾的顺子有 $j$ 个，以 $i$ 结尾的顺子有 $k$ 个且其余全部用来组成刻子的最多面子数，这样的话 $0\le j,k\le 2$ 就能做了。

UPD：可以把定义换成以 $i-1$ 开头的顺子有 $j$ 个，以 $i$ 开头的顺子有 $k$ 个，这样会比较方便。

示例程序

第二种定义：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000000;

int n,m,a[maxn+5],f[maxn+5][3][3];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&m,&n);for (int i=1,x;i<=m;i++) scanf("%d",&x),a[x]++;
    for (int i=0;i<=n;i++) for (int j=0;j<3;j++) for (int k=0;k<3;k++) f[i][j][k]=-1;f[0][0][0]=0;
    for (int i=1;i<=n;i++)
        for (int j=0;j<3;j++)
            for (int k=0,F;k<3;k++)
                if (~(F=f[i-1][j][k]))
                    for (int t=0;t<3&&j+k+t<=a[i];t++)
                        f[i][k][t]=max(f[i][k][t],F+j+(a[i]-j-k-t)/3);
    printf("%d\n",f[n][0][0]);return 0;
}

第一种定义：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000000;

int n,m,a[maxn+5],f[maxn+5][3][3];

#define KZ(i,j) ((a[i]-(j))/3)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&m,&n);for (int i=1,x;i<=m;i++) scanf("%d",&x),a[x]++;
    for (int i=1;i<=n;i++) for (int j=0;j<3;j++) for (int k=0;k<3;k++) f[i][j][k]=-1;
    f[2][0][0]=KZ(1,0)+KZ(2,0);
    for (int i=3;i<=n;i++)
        for (int j=0;j<3;j++)
            for (int k=0,F;k<3;k++)
                if (~(F=f[i-1][j][k])){
                    int lim=min(a[i-2]-j-k,a[i-1]-k);F-=KZ(i-2,j+k)+KZ(i-1,k);
                    for (int t=0;t<3&&t<=lim&&t<=a[i];t++)
                        f[i][k][t]=max(f[i][k][t],F+t+KZ(i-2,j+k+t)+KZ(i-1,k+t)+KZ(i,t));
                }
    int ans=0;for (int j=0;j<3;j++) for (int k=0;k<3;k++) ans=max(ans,f[n][j][k]);
    printf("%d\n",ans);return 0;
}