4294: 捕蛇

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:54 Solved:22

Description

传说,数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而,蛇们现在卷土重来了!圣帕特里克节是在每年的3月17日,所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。

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她捕捉完所有组的蛇之后可以达到的总浪费空间的最小值。

Input

输入的第一行包含$N$和$K$。第二行包含$N$个整数$a_1,\dots,a_N$,其中$a_i$($0 \leq a_i \leq 10^6$)为第$i$组蛇的数量。

Output

输出一个整数,为Bessie抓住所有蛇的总浪费空间的最小值。

Sample Input Copy

6 2
7 9 8 2 3 2

Sample Output Copy

3

HINT

Bessie可以设置她的捕网开始时大小为7。当她抓完第一组蛇之后,她将她的捕网的大小调整为9,保持这个大小直到抓完第4组蛇,再将捕网大小调整为3。总浪费空间为$(7-7) + (9-9) + (9-8) + (3-2) + (3-3) + (3-2) = 3$。

供题:Patrick Zhang

加入题单

上一题 下一题 算法标签: