F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:本站提供各级各类比赛备战资源(Noip提高组及以下),有意者请联系Lydsy2012@163.com,仅限教师及家长用户。
Problem 5488. -- [Usaco2018 Dec]Teamwork

5488: [Usaco2018 Dec]Teamwork

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 57  Solved: 34
[Submit][Status][Discuss]

Description

在Farmer John最喜欢的节日里,他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物,他想要获得他的
奶牛们的帮助。你可能能够想到,奶牛们本身也不是很擅长包装礼物,而Farmer John即将得到这一教训。Farmer 
John的N头奶牛(1≤N≤104)排成一行,方便起见依次编号为1…N。奶牛i的包装礼物的技能水平为si。她们的技
能水平可能参差不齐,所以FJ决定把她的奶牛们分成小组。每一组可以包含任意不超过K头的连续的奶牛(1≤K≤1
03),并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习,这一组中每一头奶牛的技能水平会变成这一
组中水平最高的奶牛的技能水平。请帮助FJ求出,在他合理地安排分组的情况下,可以达到的技能水平之和的最大
值。

Input

输入的第一行包含N和K。
以下N行按照N头奶牛的排列顺序依次给出她们的技能水平。技能水平是一个不超过10^5的正整数。

Output

输出FJ通过将连续的奶牛进行分组可以达到的最大技能水平和。

Sample Input

7 3
1
15
7
9
2
5
10

Sample Output

84
在这个例子中,最优的方案是将前三头奶牛和后三头奶牛分别分为一组,中间的奶牛单独成为一组(注意一组的奶
牛数量可以小于K)。这样能够有效地将7头奶牛的技能水平提高至15、15、15、9、10、10、10,和为84。

HINT

Source

Gold

[Submit][Status][Discuss]

HOME Back