给定 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an。
现在,请你从中挑选一些数,并将选出的数进行分组。
要求:
请问,最多可以选出多少个数进行分组?
输入格式
第一行包含两个整数 nnn 和 kkk。
第二行包含 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an。
输出格式
输出一个整数,表示可以选出的最大整数数量。
数据范围
1≤k≤n≤5000,1≤k≤n≤5000,1≤k≤n≤5000,
1≤ai≤1091≤a_i≤10^91≤ai≤109
输入样例1:
5 2
1 2 15 15 15
输出样例1:
5
输入样例2:
6 1
36 4 1 25 9 16
输出样例2:
2
输入样例3:
4 4
1 10 100 1000
输出样例3:
4
f[i][j]f[i][j]f[i][j] 表示在前 iii 个数中选,将其分为 jjj 组的方案
f[i][j]=max(f[i−1][j],f[k−1][j−1]+(i−k+1))f[i][j] = max(f[i-1][j], f[k-1][j-1] + (i - k + 1))f[i][j]=max(f[i−1][j],f[k−1][j−1]+(i−k+1))
f[i−1][j]f[i-1][j]f[i−1][j] 表示不选当前第 iii 个数,分为 jjj 组的方案
f[k−1][j−1]f[k-1][j-1]f[k−1][j−1] 表示选当前第 iii 个数,最右边的组的左边界取到第 kkk 个数的方案
kkk 满足 w[i]−w[k]<=5w[i]-w[k] <= 5w[i]−w[k]<=5 的最左边的数
#include
#includeusing 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;
}
上一篇:k8s加固 hardening