AcWing 3583. 整数分组
原题链接
中等
作者:
不幸到吃土
,
2025-01-16 22:34:26
,
所有人可见
,
阅读 3
//状态表示:f[i,j]表示从(1,i)中选方案数为j组的整数数量
/*
状态计算:考虑将原数组排序,按照最后一组为划分(设最后一组的起始下标为k,第i个元素包括在最后一组内)
(1)不选第i个元素--此时不影响最后一组的存在
f[i,j] = f[i-1,j]
(2)选第i个元素--可等价于先不选最后一组元素,再选上
f[i,j] = f[k-1,j-1] + (i-k+1)
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
int a[N];
int f[N][N];
int main(){
int n,m;
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> a[i];
}
sort(a+1,a+1+n);
for(int i=1,k=1;i<=n;i++){ //k为组数且至少为1
while(a[i] - a[k] > 5) //对数组的遍历采取双指针
k++;
//开始DP
for(int j=1;j<=m;j++){
f[i][j] = max(f[i-1][j],f[k-1][j-1] + (i-k+1));
}
}
cout << f[n][m] << endl;
return 0;
}