P6304 [eJOI 2018] 山

Innopolis 城里有 $n$ 座山，第 $i$ 座的高度为 $a_i$。 美观起见，当一座山比它两边的山（如果存在）**严格** 地高时，才能在这座山上建房子。 有一台挖掘机，每小时可以将任意一座山的高度降低 $1$，同一时间挖掘机只能在一座山上工作。山的高度可以被降为 $0$ 或负数。 请求出当 $1\leq k\leq \lceil\frac{n}{2}\rceil$ 时，建造 $k$ 座房子（即至少使得 $k$ 座山满足上面的要求）时，挖掘机至少需要工作几小时。

无

无

【样例一解释】 将山 $2$ 的高度降低 $1$，山的高度变为 $1,0,1,1,1$，此时山 $1$ 满足条件。 再将山 $4$ 的高度降低 $1$，山的高度变为 $1,0,1,0,1$，此时山 $1,3,5$ 满足条件。 --- 【数据范围】 对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^3$，$1\leq a_i\leq 10^5$。 | 子任务编号 | 分数 | 限制 | | :----------: | :----------: | :----------: | | $1$ | $0$ | 样例 | | $2$ | $7$ | $n=3,a_i\leq 100$ | | $3$ | $15$ | $n\leq 10,a_i\leq 100$ | | $4$ | $13$ | $n\leq 100,a_i\leq 100$ | | $5$ | $18$ | $n\leq 100,a_i\leq 2\times 10^3$ | | $6$ | $22$ | $n\leq 500$ | | $7$ | $25$ | 无特殊限制 | --- 来源：[eJOI2018](http://ejoi2018.org/) Problem A「Hills」 说明：翻译来自 [LOJ](https://loj.ac/problem/2813)