Codeforces Round #544 (Div. 3) E. K Balanced Teams

题意:

有n个数字，要你分成k组，要求每组内最大值与最小值的差值不超过5。求k组最多可以放多少个数。

思路：

线性DP，预计算出这个数字作为右端点时取的数字的个数，然后考虑每个数字取或者不取。

Code：

#include <bits/stdc++.h>
using namespace std;
int a[5005], b[5005], dp[5005][5005], n, m;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
		b[i] = lower_bound(a + 1, a + 1 + n, a[i] - 5) - a - 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);//不选
			dp[i][j] = max(dp[i][j], dp[b[i]][j-1] + i - b[i]);//选
		}
	}
	printf("%d", dp[n][m]);
}