题意
n个数，皆不大于m，(1 /leq n, m \leq 10^6)，求能构成的顺子和刻子的数目和的最大值。
题解
先考虑简化版，每个数只出现一遍，那明显是个水题。
然后考虑能不能限制每个数出现的次数来简化问题。全部设置不大于3次其实是不行的，毕竟优先考虑构成顺子或刻子是不行的。
例如数据1,2,2,2,3和1,2,3,3,3,4,4,5,5
但是可以注意到，三个或三个以上的相同顺子，如3个三元组(2, 3, 4)，可以看成是(2,2,2)和(3,3,3)(4,4,4)这样，所以每个三元组出线不超过2次，所以转移状态有限。
最开始是想用dp[maxm][3]的二维数字做的，但是发现不行，所以用的是三维dp
与i有关的三元顺子，有(i-2, i-1, i)和(i-1,i,i+1)和(i, i+1,i+2)，考虑如何转移到包含i+1的状态，所以dp的时候只考虑后两者。
dp[i][j][k]指的是当前使用后两者的数量分别是j和k，此时剩余数字i+1的数量是A[i+1]-j-k，更新dp[i+1][k][:]的状态
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 10;
int dp[maxn][3][3];
int A[maxn];
int n, m;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
scanf("%d%d", &n, &m);
memset(A, 0, sizeof(A));
memset(dp, -1, sizeof(dp));
dp[0][0][0] = 0;
int t;
for (int i = 0; i < n; i++) {
scanf("%d",&t);
A[t]++;
}
for (int i = 0; i <= m + 1; i++) {
for (int j = 0; j <= 2; j++) {
for (int k = 0; k <= 2; k++) {
if (dp[i][j][k] == -1) continue;
int up = A[i + 1] - j - k;
for (int tt = 0; tt <= 2 && tt <= up; tt++) {
dp[i + 1][k][tt] = max(dp[i + 1][k][tt], dp[i][j][k] + (up - tt) / 3 + tt);
}
}
}
}
printf("%d\n", dp[m + 1][0][0]);
return 0;
}
转载于:https://www.cnblogs.com/xFANx/p/11181894.html
相关资源：JAVA上百实例源码以及开源项目
