Teamwork

题目描述

在他最喜欢的节日里，农夫约翰想把礼物寄给他的朋友们。 由于他不太擅长包装礼物，他想请他的奶牛来帮忙。你可能也想得到，奶牛自己也并不擅长包装礼物——这是农夫约翰即将痛苦地领教到的一课。

农夫约翰的 $N$ 头奶牛（$1 \leq N \leq 10^4$）都站成一排，按顺序方便地编号为 $1 \ldots N$。第 $i$ 头奶牛在包装礼物方面的技能水平为 $s_i$。这些技能水平可能差异很大，因此 FJ 决定把奶牛组合成若干队伍。一个队伍可以由任意一段连续的、最多包含 $K$ 头奶牛（$1 \leq K \leq 10^3$）组成，并且任何一头奶牛不能同时属于多个队伍。 由于奶牛会互相学习，一个队伍中每头奶牛的技能水平都可以被替换为该队伍中技能最高的奶牛的技能水平。

请帮助 FJ 确定：通过最优地组队，他能够得到的技能水平总和的最大值。

输入格式

第一行输入包含 $N$ 和 $K$。接下来 $N$ 行按奶牛站立的顺序给出这 $N$ 头奶牛的技能水平。每个技能水平都是不超过 $10^5$ 的正整数。

输出格式

请输出 FJ 通过将连续的奶牛集合分组为队伍所能达到的最大技能水平总和。

7 3
1
15
7
9
2
5
10

84

提示

在这个例子中，最优方案是将前三头奶牛分为一队，将最后三头奶牛分为一队，中间那头奶牛单独成队（请记住，队伍大小可以小于 $K$）。这样等效地将 7 头奶牛的技能水平提升为 15, 15, 15, 9, 10, 10, 10，总和为 84。 题目来源：Brian Dean

标签: USACO|2018|Gold

来源

USACO|2018|Gold