#P1749. [usaco2005 open]Landscaping 地形改造
[usaco2005 open]Landscaping 地形改造
[USACO05OPEN] Landscaping G
题目描述
农夫约翰正在做一次艰难的转型,从养山羊改成养奶牛,他的农场,由于是为养山羊而设计的所以有太多的山,为了养牛就必须将它整平。但是,将山整平是件很花钱的工作,所以他要移走尽可能少的土。
由于农场很细长,所以可以用一个 和 个整数(范围 )组成的一维数组来表示,如:
1 2 3 3 3 2 1 3 2 2 1 2
上述农场的侧面图是这样的:
* * * *
* * * * * * * * *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2
一个极大的连续等高区间称为山顶,当且仅当它两边紧邻的位置都比它低,或者相应一侧是数组边界。上例共有三个山顶。要使山顶数量至多为 ,最少需要移走多少单位的土?每个位置的海拔每降低一单位,就要移走一单位的土。注意,地面的海拔只能被降低不能被升高。 对于例子,如果要减少到只有 个山顶,这需要移走 个单位的土(- 表示移走的土):
* * * -
* * * * * - - - -
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2
输入格式
第 行输入整数 和 。
之后 行,每行输入一个整数,表示这块地的海拔。
输出格式
输出一个整数,表示使山顶数量至多为 时需要移走的最少土量。
样例 #1
样例输入 #1
12 1
1
2
3
3
3
2
1
3
2
2
1
2
样例输出 #1
5
提示
对于 的数据,,。