题意：
一些数字，有两种方式组成一个三元组，[x,x,x]，[x,x+1,x+2]，每个数字只能用一次，求最多组成多少三元组。
分析：
因为每三个[x,x+1,x+2]是可以拆成[x,x,x]，[x+1,x+1,x+1]，[x+2,x+2,x+2]的，所以可以认为对于以x开始的[x,x+1,x+2]最多有两个。
于是可以dp[i][x][y]表示到第i个数字，存在x个[i-1,i,i+1]，y个[i,i+1,i+2]，最多组成多少个三元组（这些三元组的右端点在i以内，超出i三元组有x+y个，没有记录到里面）
然后转移的时候枚举多少个[i+1,i+2,i+3]。
代码：
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<cctype> #include<set> #include<queue> #include<vector> #include<map> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;return x*f; } const int N = 1e6 + 10; LL f[N][3][3], a[N]; int main() { int n = read(), m = read(); for (int i = 1; i <= n; ++i) a[read()] ++; memset(f, -0x3f, sizeof(f)); f[0][0][0] = 0; for (int i = 1; i <= m; ++i) { for (int x = 0; x < 3; ++x) for (int y = 0; y < 3; ++y) for (int z = 0; z < 3; ++z) { if (a[i] < x + y + z) continue; f[i][x][y] = max(f[i][x][y], f[i - 1][z][x] + (a[i] - x - y - z) / 3 + z); } } cout << f[m][0][0]; return 0; }
原文：https://www.cnblogs.com/mjtcn/p/10357155.html