AcWing 3583. 整数分组
原题链接
中等
作者:
术
,
2021-05-30 15:53:10
,
所有人可见
,
阅读 312
#include <iostream>
#include <algorithm>
using namespace std;
const int N=5005;
int a[N];
int dp[N][N];//dp(i,j)表示前i个元素选j组最大值
int n,k;
/*
连续区间
最优解可以无重合区间
最后一段区间尽可能长
满足这三个条件就可用dp
*/
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]=abs(a[i]);
}
sort(a+1,a+n+1);
for(int i=1,p=1;i<=n;i++){
while(a[i]>a[p]+5) p++;//找出离i最近的可满足元素
for(int j=1;j<=k;j++)//
dp[i][j]=max(dp[i-1][j],dp[p-1][j-1]+i-p+1);//选i和不选i
}
cout<<dp[n][k];
//cout << "Hello world!" << endl;
return 0;
}