题目描述
本题译自 eJOI2018 Problem A. Hills
Innopolis 城里有 n 座山,第 i 座的高度为 ai。
美观起见,当一座山比它两边的山(如果存在)严格地高时,才能在这座山上建房子。
有一台挖掘机,每小时可以将任意一座山的高度降低 1,同一时间挖掘机只能在一座山上工作。山的高度可以被降为 0 或负数。
请求出当 1≤k≤⌈2n⌉ 时,建造 k 座房子(即至少使得 k 座山满足上面的要求)时,挖掘机至少需要工作几小时。
输入格式
第一行,1 个整数 n (1≤n≤5000)。
第二行,n 个整数 a1,a2,a3,⋯an,表示数列 {ai} ,其中 1≤ai≤105 。
输出格式
一行,⌈2n⌉ 个整数,第 i 个整数表示 k=i 时的答案。
5
1 1 1 1 1
1 2 2
3
1 2 3
0 2
5
1 2 3 2 2
0 1 3
数据范围与提示
数据限制
子任务编号 |
分数 |
限制 |
1 |
0 |
样例 |
2 |
7 |
n=3,ai≤100 |
3 |
15 |
n≤10,ai≤100 |
4 |
13 |
n≤100,ai≤100 |
5 |
18 |
n≤100,ai≤2000 |
6 |
22 |
n≤500 |
7 |
25 |
无特殊限制 |