AcWing 3583 整数分组(01背包 + 双指针)

原题链接
本题是比较明显的01背包，选或者不选，中间可以用双指针找到最后可以选到的区间长度，那么如果选当前最后一个区间的话最后就要求这个区间前面的长度要最大
状态表示： f[i][j]表示从区间1~i中选出j组
状态计算：这里可以画图看一下，我们如果选最后一段，那么最后一段长度是确认的，决定是否是最大值就是前面的值，假设我们选了k组。我们有两个指针i, j，i指向当前区间的左端点，j是右端点，那么我们需要左端点j前面那一段最大也就是f[j - 1][k - 1]最大，状态转移方程便是f[i][k] = f[j - 1][k - 1] + i - j + 1;
如果不选当前这个区间的话，那么状态转移方程便是f[i][k] = f[i - 1][k];

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;
int a[N], f[N][N];
int main() {
  int n, m;
  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, j = 1; i <= n; i++) {
    while (a[i] - a[j] > 5) j++;
    for (int k = 1; k <= m; ++k) {
      f[i][k] = max(f[i - 1][k], f[j - 1][k - 1] + i - j + 1);
    }
  }
  printf("%d\n", f[n][m]);
  return 0;
}