问题 CD: 消消乐
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：33
解决：7
题目描述
你正在玩消消乐游戏，一共有 $n$ 列砖块，第 $i$ 列有 $A_i$ 个砖块。
游戏开始前，你可以使用技能，选择至多 $k$ 列砖块，将它们的数量改变成区间 $[0,10^9]$ 内的任意整数。（可以各不相同）
游戏开始后，你可以花费一点体力，将区间 $[i,j]$ 列的砖块均消去一个，但是该区间在消除前不能有砖块数是0的列
请问你最少需要多少体力可以把砖块全部消去？
游戏开始前，你可以使用技能，选择至多 $k$ 列砖块，将它们的数量改变成区间 $[0,10^9]$ 内的任意整数。（可以各不相同）
游戏开始后，你可以花费一点体力，将区间 $[i,j]$ 列的砖块均消去一个，但是该区间在消除前不能有砖块数是0的列
请问你最少需要多少体力可以把砖块全部消去？
输入
输入共两行
第一行，两个整数 $n,k$ $(1 \leq k \leq n \leq 300)$
第二行，$n$ 个整数，代表$A_i$ $(0 \leq A_i \leq 10^9)$
第一行，两个整数 $n,k$ $(1 \leq k \leq n \leq 300)$
第二行，$n$ 个整数，代表$A_i$ $(0 \leq A_i \leq 10^9)$
输出
输出一个整数，代表最小花费体力
样例输入 复制
4 1
2 3 4 1样例输出 复制
3提示
样例解释:
共有4列砖块，你有1次改变砖块的机会。
可以将第3列砖块改成2个，现在的局面是:2 3 2 1
第一次，选择区间$[1,4]$消去，变成:1 2 1 0
第二次，选择区间$[1,3]$消去，变成:0 1 0 0
第三次，选择区间$[2,2]$消去，变成:0 0 0 0
可自证，这个策略花费的体力是最少的，花费了$3$点
共有4列砖块，你有1次改变砖块的机会。
可以将第3列砖块改成2个，现在的局面是:2 3 2 1
第一次，选择区间$[1,4]$消去，变成:1 2 1 0
第二次，选择区间$[1,3]$消去，变成:0 1 0 0
第三次，选择区间$[2,2]$消去，变成:0 0 0 0
可自证，这个策略花费的体力是最少的，花费了$3$点