Hills
Time limit1sMemory limit512 MB
Lower consecutive hills to form k peaks in n hills so that at least k hills exceed both neighbors, minimizing total height reductions, for every k from 1 to ceil(n/2).
- Level
Medium7 of 10
- Topics
- Dynamic programming, Greedy, Array
- Solved
- No attempts yet
Problem
Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from never-ending city construction.
From the window in your room, you see a sequence of n hills, where the i-th hill has height ai. The Innopolis administration wants to build some houses on the hills. For the sake of city appearance, a house can be built only on a hill that is strictly higher than its neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on the hills with heights 5 and 6 only.
The Innopolis administration has an excavator that can decrease the height of an arbitrary hill by one in one hour. The excavator can only work on one hill at a time. It is allowed to decrease hills down to zero height, or even to negative values. Increasing the height of any hill is impossible. The city administration wants to build k houses, so there must be at least k hills that satisfy the condition above. What is the minimum time required to adjust the hills to achieve the administration's plan?
However, the exact value of k is not yet determined, so could you please calculate answers for all k in the range 1 ≤ k ≤ ⌈n/2⌉? Here ⌈n/2⌉ denotes n divided by two, rounded up.
Input
The first line of input contains the single integer n (1 ≤ n ≤ 5000), the number of hills in the sequence. The second line contains n integers ai (1 ≤ ai ≤ 100 000), the heights of the hills in the sequence.
Output
Print exactly ⌈n/2⌉ numbers separated by spaces. The i-th printed number must be the minimum number of hours required to level the hills so that it becomes possible to build i houses.
Notes
In the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour. The sequence of heights then becomes 1, 0, 1, 1, 1, and the first hill becomes suitable for construction.
In the first example, to get at least two or at least three suitable hills, one can decrease the second and the fourth hills. The sequence of heights then becomes 1, 0, 1, 0, 1, and hills 1, 3, 5 become suitable for construction.