#2813. 「eJOI2018」山

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: hiuseues2

题目描述

本题译自 eJOI2018 Problem A. Hills

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

输入格式

第一行, 1 个整数 n\ (1 \le n \le 5000)
第二行, n 个整数 a_1, a_2, a_3, \cdots a_n ,表示数列 \{a_i\} ,其中 1 \le a_i \le 10^5

输出格式

一行, \lceil \frac{n}{2} \rceil 个整数,第 i 个整数表示 k=i 时的答案。

样例

样例输入 1

5
1 1 1 1 1

样例输出 1

1 2 2

样例解释 1

将山 2 的高度降低 1 ,山的高度变为 1, 0, 1, 1, 1 ,此时山 1 满足条件。
再将山 4 的高度降低 1 ,山的高度变为 1, 0, 1, 0, 1 ,此时山 1, 3, 5 满足条件。

样例输入 2

3
1 2 3

样例输出 2

0 2

样例输入 3

5
1 2 3 2 2

样例输出 2

0 1 3

数据范围与提示

数据限制

子任务编号 分数 限制
1 0 样例
2 7 n = 3, a_i \le 100
3 15 n \le 10, a_i \le 100
4 13 n \le 100, a_i \le 100
5 18 n \le 100, a_i \le 2000
6 22 n \le 500
7 25 无特殊限制