第 1 题 选数 (numbers)

CSP-S 复赛模拟赛 28 · 时间限制 1.0 s · 空间限制 256 MB · 97 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 numbers.in，输出文件 numbers.out。

KOI 2020 — 第 2 次选拔 (2차대회) 第 5 试

题目描述

$N$ 个自然数排成一排。你需要从中选 $K$ 个，且必须一次性把 $K$ 个全部选出。

对于你选出的每一个数，都要计算它的得分：该数本身的值，减去它左边被选中的数的个数。把选出的每个数的得分相加，就是总分。你需要选择 $K$ 个数，使总分最大。

例如 $N = 5$，给出的自然数依次为 $2\ 3\ 1\ 2\ 1$，$K = 3$。如果选第一个 $2$ 和两个 $1$，各数的得分为 $2\ 0\ -1$，总分是 $1$。如果选第一个 $2$、$3$ 以及第二个 $2$，各数的得分是 $2\ 2\ 0$，总分是 $4$。本例中总分的最大值是 $4$。

给定 $N$ 个自然数组成的数列和正整数 $K$，输出总分的最大值。

输入格式

第一行给出 $N$ 和 $K$，中间用一个空格隔开。

第二行给出 $N$ 个自然数，中间用一个空格隔开。

输出格式

输出一行一个整数，表示从给定的 $N$ 个数中选 $K$ 个时总分的最大值。

数据范围

• $1 \le N \le 5\,000$
• $1 \le K \le N$
• 给出的自然数均为 $1$ 到 $100\,000$ 之间的整数。

子任务

1. （4 分）$N \le 3$。
2. （25 分）$N \le 20$。
3. （7 分）$K = 1$。
4. （9 分）$K = 2$。
5. （15 分）给出的 $N$ 个数已按单调不减顺序排好。即对每个数，其左边只有不大于它的值，右边只有不小于它的值。
6. （40 分）无额外限制。

样例

样例 1

输入：

5 3
2 3 1 2 1

输出：

4

样例 2

输入：

6 2
4 1 5 2 6 3

输出：

10