Laminate

题目描述

我们将在一个有 $10^9$ 行和 $N$ 列的白色方格网格中，通过将某些方格涂成黑色来创作一幅作品。
当前的计划如下：对于从左数第 $i$ 列，我们将涂黑该列自底部起的 $H_i$ 个方格，并且不涂该列中的其他方格。
在开始工作之前，你可以选择至多 $K$ 列（可以为零）并将这些列的 $H_i$ 的值更改为你选择的任意整数，范围在 $0$ 到 $10^9$（含）之间。
不同的列可以选择不同的值。
然后，你将通过重复以下操作来创建修改后的作品：

在同一行中选择一个或多个连续的方格并将它们涂成黑色。（已经涂成黑色的方格可以再次涂色，但根据修改后的计划不应被涂色的方格不得被涂色。）

求你需要执行该操作的最小次数。

输入格式

输入按以下格式从标准输入给出： $N$ $K$ $H_1$ $H_2$ $...$ $H_N$

输出格式

输出所需的最少操作次数。

4 1
2 3 4 1

3

6 2
8 6 9 1 2 1

7

10 0
1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000

4999999996

提示

$1 \leq N \leq 300$ $0 \leq K \leq N$ $0 \leq H_i \leq 10^9$ 输入中的所有数值均为整数。例如，通过将 $H_3$ 改为 $2$，你可以通过以下三次操作来创建修改后的作品：

将自底部第 $1$ 行中从左数第 $1$ 到第 $4$ 个方格涂黑。 将自底部第 $2$ 行中从左数第 $1$ 到第 $3$ 个方格涂黑。 将自底部第 $3$ 行中从左数第 $2$ 个方格涂黑。

标签: AtCoder|abc145F

来源

AtCoder|abc145F