Snakes

题目描述

传说中，圣帕特里克在一千多年前将所有蛇从 Mooland 驱逐了出去。然而，蛇后来又回到了 Mooland！圣帕特里克节是在 3 月 17 日，所以 Bessie 将通过把所有蛇彻底赶出 Mooland 来纪念圣帕特里克。 Bessie 带着一张网来捕捉分布在一条直线上的 $N$ 组蛇 $(1 \leq N \leq 400)$。Bessie 必须按照这些组在直线上出现的顺序，捕捉每一组中的所有蛇。每当 Bessie 捕捉完一组，她可以把蛇放进笼子里，并在下一组开始时使用一张空网。 大小为 $s$ 的网表示 Bessie 可以捕捉任意一组包含 $g$ 条蛇的组，其中 $g \leq s$。但是，每当 Bessie 用大小为 $s$ 的网捕捉一组大小为 $g$ 的蛇时，她会浪费 $s - g$ 的空间。Bessie 的网可以从任意大小开始，并且她可以改变网的大小 $K$ 次 $(1 \leq K < N)$。 请告诉 Bessie，在捕捉完所有组之后，她所能累计的总浪费空间的最小值。

输入格式

第一行包含 $N$ 和 $K$。第二行包含 $N$ 个整数 $a_1,\dots,a_N$，其中 $a_i$（$0 \leq a_i \leq 10^6$）表示第 $i$ 组中的蛇的数量。

输出格式

输出一个整数，表示 Bessie 捕捉完所有蛇后浪费空间的最小值。

6 2
7 9 8 2 3 2

3

提示

Bessie 的网从大小 7 开始。她捕捉完第一组蛇后，将网的大小改为 9，并保持该大小直到第 4 组蛇，此时她将网的大小改为 3。总浪费空间为 $(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3.$ 题目来源：Patrick Zhang

标签: USACO|2019|Gold

来源

USACO|2019|Gold