思路

先将原序列排序，按最优解问题分析

最优解一定可以有的性质

1. 每个区间内连续
2. 区间之间没有交集
3. 最后一段区间尽可能长

闫式dp

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 5050;
int w[i];
int f[N][N];
int n,k;

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) cin >> w[i];
    sort(w + 1,w + n + 1);
    for(int i = 1, k = 1; i <= n; i ++){ //i和k维护的是最后一个区间的最大范围
        while(w[i] - w[k] > 5){
            k ++;                   //故当i和k的区间不满足任意两个差不超过5时，将指针k移到满足条件的最大值
        }
        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;
}