← 返回题目列表

AtCoder · abc145_f

F. 层压板

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们将通过将白色正方形网格中的一些正方形涂成黑色来创建艺术品 10^9 行和 N 列。
目前的计划如下: i从左边算起,我们将绘制 H_i 最底部的方块,并且不会绘制该列中的其他方块。
开始工作之前,您最多可以选择 K 列(可能为零)并更改 H_i 将这些列更改为您选择的任意整数 0 和 10^9 (含)。
可以为不同的列选择不同的值。

然后,您将通过重复以下操作来创建修改后的图稿:

  • 选择一排中的一个或多个连续方块并将其涂成黑色。 (已涂黑的方格可重新涂漆,但未按修改方案涂漆的方格不应涂漆。)

找出执行此操作所需的最少次数。

约束

  • 1 \leq N \leq 300
  • 0 \leq K \leq N
  • 0 \leq H_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
H_1 H_2 ... H_N

输出

打印所需的最少操作数。


示例输入 1

4 1
2 3 4 1

示例输出 1

3

例如,通过更改值 H_3 to 2,您可以通过以下三个操作创建修改后的图稿:

  • 漆黑 1-st 通过 4从左边开始第一个方格 1- 倒数第 1 行。
  • 漆黑 1-st 通过 3- 左起第 d 个方格 2- 倒数第二行。
  • 漆黑 2- 左起第一个方块 3- 倒数第三行。

示例输入 2

6 2
8 6 9 1 2 1

示例输出 2

7

示例输入 3

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

示例输出 3

4999999996