K Balanced Teams CodeForces - 1133E (Dp)

题意：

给出 n 个数，选取其中若干个数分别组成至多 k 组，要求每组内最大值与最小值的差值不超过5，求最后被选上的总人数。

题解：

将a[1∼n] 从小到大排序，

f[i][j] 表示到第 i 个数为止，已经组成 j 组，最多可以包含多少个数。

那么，考虑第 i 个数选取与否，如果不选，那么 , 

如果选，那么必然是第 i 个数所在组人数加上前面那些组人数，假设 p 表示距离 a[i]左侧最远的那个位置（满足 ），这里是指p之前的那些组的人数

题目链接：

https://cn.vjudge.net/problem/CodeForces-1133E

参考：

https://www.cnblogs.com/dilthey/p/10804527.html

#include<iostream> #include<algorithm> #include<cstring> using namespace std; int n, k; const int maxn = 5000 + 10; int a[maxn]; int f[maxn][maxn]; int main() { cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; sort(a+1, a + n + 1); int p = 1; int ans = 1; memset(f, 0, sizeof(f)); f[1][1] = 1; for(int i = 2; i <= n; i++) { while(p < i && a[i] - a[p] > 5) // p~i为一组 p++; for(int j = 1; j <= min(k, i); j++) //i可能小于k，也可能大于k（这时就应限制大小） { f[i][j] = max(f[i-1][j], (i - p + 1) + f[p-1][j-1]); ans = max(ans, f[i][j]); } } cout << ans << endl; }

注：发现从数组从下标1开始输入比较稳妥，可以避免样例1发生p-1=-1的情况