dp
子集
- 用第i个数及大于等于第i个数-5的所有数 新增一个组
$$ f[i][j] = f[t][j-1] + i-t (t = a[t]<a[i]-5) $$
- 不用第i个数
$$ f[i][j] = f[i-1][j] $$
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5010;
int f[N][N],a[N];
int main()
{
int n,K;
cin>>n>>K;
// f[i][j] 到第i个数结尾分为j组最大数量
/*
子集
1 用第i个数及大于等于第i个数-5的所有数 新增一个组 f[i][j] = f[t][j-1] + 1 (t = a[t]<a[i]-5)
2 不用第i个数 f[i][j] = f[i-1][j]
*/
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=K;j++)
{
// 不用第i个数
f[i][j] = f[i-1][j];
int t = i;
while(t>0 && a[i]-a[t]<=5)t--;
// 用第i个数
f[i][j] = max(f[i][j], f[t][j-1]+i-t);
}
}
cout<<f[n][K];
return 0;
}