整数分组（冬季每日一题 16）

给定 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

现在，请你从中挑选一些数，并将选出的数进行分组。

要求：

1. 选出的数最多划分为 $k$ 组（至少 $1$ 组）。
2. 同一组内，任意两数之差的绝对值不超过 $5$。
3. 所选出的数尽可能多。

请问，最多可以选出多少个数进行分组？

输入格式
第一行包含两个整数 $n$ 和 $k$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

输出格式
输出一个整数，表示可以选出的最大整数数量。

数据范围
$1\le k\le n\le 5000,$
$1\le a_i\le 10^9$
输入样例1：

5 2
1 2 15 15 15
1
2

输出样例1：

5
1

输入样例2：

6 1
36 4 1 25 9 16
1
2

输出样例2：

2
1

输入样例3：

4 4
1 10 100 1000
1
2

输出样例3：

4
1

---

$f[i][j]$ 表示在前 $i$ 个数中选，将其分为 $j$ 组的方案
$f[i][j]=max(f[i-1][j],f[k-1][j-1]+(i-k+1))$
$f[i-1][j]$ 表示不选当前第 $i$ 个数，分为 $j$ 组的方案
$f[k-1][j-1]$ 表示选当前第 $i$ 个数，最右边的组的左边界取到第 $k$ 个数的方案
$k$ 满足 $w[i]-w[k]<=5$ 的最左边的数

#include
#include

using namespace std;

const int N = 5010;

int n, m;
int w[N], f[N][N];

int main(){
    
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
    sort(w + 1, w + n + 1);
    
    for(int i = 1, k = 1; i <= n; i++){
        
        while(w[i] - w[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));
    }
    
    printf("%d\n", f[n][m]);
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28