我…我我把这…这这题切了？？？
说实话这题的确不难，只是我看到有大佬没做出来有点慌……
突然发现这题是我在洛谷的第500个AC呢。那就更要写篇题解纪念一下了。
思路
容易想到一个贪心：把有三个的都取完，然后随便搞后面的。
这显然是错的……
但你进一步思考发现：对于三元组\(\{x-2,x-1,x\}\)，它最多取\(2\)次，否则就可以变成多个\(\{x,x,x\}\)后再重新搞。
那么就容易想到DP了。
设\(dp_{i,j,k}\)表示考虑到第\(i\)位，钦定第\(i\)位已经用掉了\(j\)个，第\(i-1\)位已经用掉了\(k\)个，能得到的三元组个数。
转移时枚举选几个\(\{i-2,i-1,i\}\) ，得到转移方程：
\[dp_{i,j,k}=\max_{l=0}^2\{dp_{i-1,k+l,l}+\lfloor \frac{cnt_i-l-j}{3}\rfloor +l\}
\]
\]
最后\(ans=dp_{m,0,0}\)。
注意DP时一个位置会被钦定两次，所以\(0\leq j,k\leq 4\)。
代码
#include<bits/stdc++.h>
namespace my_std{
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define go(x) for (int i=head[x];i;i=edge[i].nxt)
#define sz 1010101
typedef long long ll;
template<typename T>
inline void read(T& t)
{
t=0;char f=0,ch=getchar();
double d=0.1;
while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
if(ch=='.')
{
ch=getchar();
while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();
}
t=(f?-t:t);
}
template<typename T,typename... Args>
inline void read(T& t,Args&... args){read(t); read(args...);}
void file()
{
#ifndef ONLINE_JUDGE
freopen("a.txt","r",stdin);
#endif
}
// inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;
int n,m;
int cnt[sz];
int dp[sz][5][5];
int main()
{
file();
int x;
read(n,m);
rep(i,1,n) read(x),++cnt[x];
memset(dp,~0x3f,sizeof(dp));
dp[0][0][0]=0;
rep(i,0,min(4,cnt[1])) dp[1][i][0]=(cnt[1]-i)/3;
rep(i,2,m)
{
rep(j,0,4)
{
if (j>cnt[i]) break;
rep(k,0,4)
{
if (k>cnt[i-1]) break;
rep(l,0,2)
{
if (j+l>cnt[i]||k+l>cnt[i-1]||l>cnt[i-2]||k+l>4) break;
dp[i][j][k]=max(dp[i][j][k],dp[i-1][k+l][l]+(cnt[i]-l-j)/3+l);
}
}
}
}
cout<<dp[m][0][0];
}