#P9835. [USACO05OPEN] Landscaping G

[USACO05OPEN] Landscaping G

题目描述

农夫约翰正在做一次艰难的转型,从养山羊改成养奶牛,他的农场,由于是为养山羊而设计的所以有太多的山,为了养牛就必须将它整平。但是,将山整平是件很花钱的工作,所以他要移走尽可能少的土。

由于农场很细长,所以可以用一个 nnnn 个整数(范围 [1,106][1,10^6])组成的二维的数组来表示,如:

1 2 3 3 3 2 1 3 2 2 1 2

上述农场的侧面图是这样的:

    * * *     *
  * * * * *   * * *   *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

一个或是一些连续等高的地面,如果它左边或是右边的海拔都比它低的话,就被称为山顶,上面的例子就有三个山顶。 确定如果要使地图上仅有 kk 个山顶,至少要移走多少体积的土(每块地面减少一单位海拔需移走一单位的土)。注意,地面的海拔只能被降低不能被升高。 对于例子,如果要减少到只有 11 个山顶,这需要移走 2+1+1+1=52+1+1+1=5 个单位的土(- 表示移走的土):

    * * *     -
  * * * * *   - - -   -
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2

输入格式

11 行输入整数 nnkk

之后 nn 行,每行输入一个整数,表示这块地的海拔。

输出格式

如果仅能有 kk 个山顶至少要移走多少土。

12 1
1
2
3
3
3
2
1
3
2
2
1
2

5

提示

对于 100%100\% 的数据,1n1031 \leq n \leq 10^31k251 \leq k \leq 25