Hills
Contest: Codeforces Round 500 (Div. 1) [based on EJOI]
Difficulty rating: 1900
Tags: dp

Welcome to Innopolis city. Throughout the whole year, Innopolis citizens suffer from everlasting city construction.

From the window in your room, you see the sequence of n hills, where i-th of them has height ai. The Innopolis administration wants to build some houses on the hills. However, for the sake of city appearance, a house can be only built on the hill, which is strictly higher than neighbouring hills (if they are present). For example, if the sequence of heights is 5, 4, 6, 2, then houses could be built on 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 up to zero height, or even to negative values. Increasing 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 range $$1 \leq k \leq \left\lceil \frac{n}{2} \right\rceil$$? Here $$\left\lceil \frac{n}{2} \right\rceil$$ denotes n divided by two, rounded up.

Input format:
The first line of input contains the only integer n (1 ≤ n ≤ 5000)—the number of the hills in the sequence.

Second line contains n integers ai (1 ≤ ai ≤ 100 000)—the heights of the hills in the sequence.

Output format:
Print exactly $$\left\lceil \frac{n}{2} \right\rceil$$ numbers separated by spaces. The i-th printed number should be equal to the minimum number of hours required to level hills so it becomes possible to build i houses.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In the first example, to get at least one hill suitable for construction, one can decrease the second hill by one in one hour, then the sequence of heights 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, then the sequence of heights becomes 1, 0, 1, 0, 1, and hills 1, 3, 5 become suitable for construction.

Example input:
5
1 1 1 1 1

Example output:
1 2 2

Example input:
3
1 2 3

Example output:
0 2

Editorial:
The problem's short statement is: "we allowed to decrease any element and should create at least k local maximums, count the minimum number of operations for all k".
Notice, that any set of positions, where no positions are adjacent could be made to be local maximums — we just need to decrease the neighbouring hills to some value.
Let's introduce the following dynamic programming:
dp[prefix][local_maxs] – the minimum cost if we analyze only given prefix, have the specified number of local maximums ("good hills to build on") and we make a local maximum in the last hill of this prefix.
Th dumb implementation of this leads to O(n2) states and O(n4) time — in each state we can brute force the previous position of local maximum (n) and then calculate the cost of patching the segment from previous local maximum to current one.
A more attentive look says that it is, in fact O(n3) solution — on the segment only first and last elements need to be decreased (possibly first and last elements are same).
To get the full solution full solution in O(n2) we need to optimize dp a little bit. As we noticed in the previous paragraph, there is one extreme situation, when the first and elements are same, let's handle this transition by hand in O(1) for each state.
Otherwise, funny fact, the cost of the segment strictly between local maximums is the cost of it's left part plus it'cost of it's right part. Seems like something we can decompose, right?
Since our goal is to update state (prefix, local) now the right part is fixed constant for all such transitions. And we need to select minimum value of dp[i][local - 1] + cost(i, i + 1) where i <  = prefix - 3.
This can be done by calculating a supplementary dp during the primarily dp calculation — for example we can calculate f[pref][j] = min dp[i][j] + cost(i, i + 1) for i ≤ pref.