P12076 [OOI 2025] Cute Subsequences

[试题来源](https://inf-open.ru/2024-25/final-materials/)。

给定一个长度为 $n$ 的正整数数组 $a_1, a_2, \ldots, a_n$，以及一个正整数 $k$。你需要将该数组划分为 $k$ 个非空子序列，使得每个元素恰好属于一个子序列。 子序列指的是从原始序列中删除若干个元素（可以为零），但不改变剩余元素的相对顺序后所得到的序列。 设第 $i$ 个子序列包含的是原数组中下标为 $j_1 < \ldots < j_l$ 的元素。该子序列的「价值」定义为 $\max\limits_{1 \le m \le l}(a_{j_m} + m)$。 将数组划分为 $k$ 个子序列的「代价」是这 $k$ 个子序列的价值之和。 请你计算出数组在划分方案最优时所能获得的最大代价。

第一行包含两个正整数 $n$ 和 $k$（$1 \le k \le n \le 500\,000$）—— 分别表示数组的长度以及要划分出的子序列数量。 第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 表示数组中的元素。

输出一个整数，表示将给定数组划分为 $k$ 个非空子序列所能获得的最大代价。

**样例解释** 在样例中，可以将数组划分为 $[3, 10]$、$[7]$、$[1, 2]$。那么答案为： $$(10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24.$$ 本题的测试点共包含六个分组。只有当某个分组的所有测试点**以及**其依赖的所有分组测试点均通过时，才能获得该分组的分数。 | Subtask | 分值 | 限制条件：$n$ | 限制条件：$k$ | 依赖分组 | 说明 | | :--- | :--- | :------------- | :------------- | :------- | :----------------------------- | | 0 | 0 | -- | -- | -- | 样例测试点。 | | 1 | 14 | $n \le 8$ | -- | 0 | | | 2 | 19 | -- | $k = 2$ | -- | | | 3 | 17 | -- | -- | -- | 满足 $a_{i+1} \le a_i$。 | | 4 | 21 | -- | -- | -- | 满足 $a_{i+1} \ge a_i - 1$。 | | 5 | 15 | $n \le 1000$ | -- | 0, 1 | | | 6 | 14 | -- | -- | 0 -- 5 | |