整数分组(冬季每日一题 16)
admin
2024-02-15 13:03:25
0

给定 nnn 个整数 a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​。

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

要求:

  1. 选出的数最多划分为 kkk 组(至少 111 组)。
  2. 同一组内,任意两数之差的绝对值不超过 555。
  3. 所选出的数尽可能多。

请问,最多可以选出多少个数进行分组?

输入格式
第一行包含两个整数 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;
}

相关内容

热门资讯

良辰美景接近打成语 良辰美景接近打成语【风前月下】:指良辰美景。【良辰媚景】:美好的时光和景物。同“良辰美景”。【良时美...
“给”字开头成语有哪些? “给”字开头成语有哪些? “给”字开头成语:无。给的成语:户给人足、家给民足、家给人足、人给家足、自...
肺上有肿瘤治得好吗? 肺上有肿瘤治得好吗?有一定的效果肺脏肿瘤不好治疗,临床上肺脏恶性肿瘤属于肺癌。在治疗上早期可以通过手...
怎样做才能让对方感觉到你真的很... 怎样做才能让对方感觉到你真的很在乎他?多给她一些精神上的关心和爱护,多体贴她,要包容她。对她周围的一...
帮忙写篇作文! 帮忙写篇作文!今天轮到我给孩子们做班主任,一天过后,心情很激动。看着孩子们可爱的笑脸,就仿佛看到我童...
有人说郭德纲的相声比较俗,那么... 有人说郭德纲的相声比较俗,那么相声“俗雅”的解释权在谁手里?我认为相声俗雅的解释权应该在观众手里,而...
2024年中国旅游者出境满意度... 今天分享的是:2024年中国旅游者出境满意度报告 报告共计:28页 2024年中国出境游满意度报告:...
7.15上海游戏峰会:解码全球... 2025年7月15日,由上海市新闻出版局指导、上海市网络游戏行业协会主办的上海游戏精英峰会暨上海游戏...
新华全媒头条|共绘雪域高原同心... (配本社同题文字稿) 孩子们在位于西藏那曲市色尼区南部新城的“温暖嘉·色尼城市书房”看书(202...
小学楼道里涂鸦墙用水粉颜料可以... 小学楼道里涂鸦墙用水粉颜料可以吗,墙上是油漆涂过的不可以,用水粉一擦就掉了,用丙烯颜料,和水粉感觉差...
有什么科幻小故事,短一些? 有什么科幻小故事,短一些? 遇见外星人一天,我在公园里散步。突然,一个像盘子一样发着许多光的东西...
幼儿园安吉室外投放哪些材料 幼儿园安吉室外投放哪些材料幼儿园安吉室外投放材料滚筒、积木、长板、木箱、梯子、沙水、锅、碗、瓢、盆、...
爱情的十字路口我该怎么选择? 爱情的十字路口我该怎么选择?真爱掌握在你自己手中!爱他就努力争取,不顾一切!还不是很爱他,那就等等,...
有没有和《恶魔狂想曲之明日骄阳... 有没有和《恶魔狂想曲之明日骄阳》差不多精彩的小说?女主角很多,个性鲜明,主角多情但不滥情,富于正义文...
功利主义是否认为道德应该是一种... 功利主义是否认为道德应该是一种绝对的命令?最源头的定义是边沁的观点,使所有人的快乐最大化。之后有缪尔...
什么是CC猫啊 什么是CC猫啊CC是一只可爱活泼的猫猫,因为诞生于沪江网校所以全称:沪江网校CC猫。CC猫常常出没于...
美剧迷失第三季好看吗? 美剧迷失第三季好看吗?个人觉得,迷失第一季还不错,很惊异.越往后看越没意思.相信我你会越看越迷失的....
求推荐一些奇幻和爱情主题的动漫 求推荐一些奇幻和爱情主题的动漫刀剑神域 强烈推荐妖精的尾巴哈尔的移动城堡~~强烈推荐刀剑神域!!!...
张晓风的这篇柳运用什么的修辞手... 张晓风的这篇柳运用什么的修辞手法张晓风的这片《柳》运用了比喻,对比的修辞手法。希望我的解答对我有帮助...