bzoj#P1749. [usaco2005 open]Landscaping 地形改造
[usaco2005 open]Landscaping 地形改造
题目描述
农夫约翰正在做一次艰难的转型,从养山羊改成养奶牛,他的农场,由于是为养山羊而设计的所以有太多的山,为了养牛就必须将它整平。但是,将山整平是件很花钱的工作,所以他要移走尽可能少的土。
由于农场很细长,所以可以用一个 和 个整数(范围 )组成的二维的数组来表示,如:
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
其中 -
表示移走的土。
输入格式
第 行输入整数 和 。之后 行,每行输入一个整数,表示这块地的海拔。
输出格式
如果仅能有 个山顶至少要移走多少土。
12 1
1
2
3
3
3
2
1
3
2
2
1
2
5
数据规模与约定
对于 的数据,,。
题目来源
Gold