Clear the Multiset
Contest: Educational Codeforces Round 94 (Rated for Div. 2)
Difficulty rating: 2200
Tags: data structures, divide and conquer, dp, greedy

You have a multiset containing several integers. Initially, it contains $$$a_1$$$ elements equal to $$$1$$$, $$$a_2$$$ elements equal to $$$2$$$, ..., $$$a_n$$$ elements equal to $$$n$$$.

You may apply two types of operations:

- choose two integers $$$l$$$ and $$$r$$$ ($$$l \le r$$$), then remove one occurrence of $$$l$$$, one occurrence of $$$l + 1$$$, ..., one occurrence of $$$r$$$ from the multiset. This operation can be applied only if each number from $$$l$$$ to $$$r$$$ occurs at least once in the multiset;
- choose two integers $$$i$$$ and $$$x$$$ ($$$x \ge 1$$$), then remove $$$x$$$ occurrences of $$$i$$$ from the multiset. This operation can be applied only if the multiset contains at least $$$x$$$ occurrences of $$$i$$$.

What is the minimum number of operations required to delete all elements from the multiset?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Output format:
Print one integer — the minimum number of operations required to delete all elements from the multiset.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
4
1 4 1 1

Example output:
2

Example input:
5
1 0 1 0 1

Example output:
3

Editorial:
Let's solve the problem by dynamic programing. Let $$$dp_{i, j}$$$ be the minimum number of operations to delete all elements from $$$1$$$ to $$$i$$$, if we have $$$j$$$ "unclosed" operations of the first type. In each transition, we either advance to the right (and possibly "close" some operations of the second type, so we go from $$$dp_{i, j}$$$ to $$$dp_{i + 1, \min(a_{i + 1}, j)}$$$, adding $$$1$$$ to the answer if $$$j < a_{i + 1}$$$), or "open" a new operation of the second type (so we go from $$$dp_{i, j}$$$ to $$$dp_{i, j + 1}$$$, adding $$$1$$$ to the answer). This solution runs in $$$O(nA)$$$, which is too slow.
The observation that helps us to speed this up is that we have to use only values from the array $$$a$$$ as the second state of our dynamic programming. Let's prove it.
The proof begins here
Let's call an integer $$$i$$$ saturated if all occurrences of $$$i$$$ were deleted by operations of the first type. Also, let's denote $$$c_i$$$ as the number of elements equal to $$$i$$$ deleted by the operations of the first type (so, $$$i$$$ is saturated iff $$$a_i = c_i$$$).
Suppose $$$k$$$ is the minimum integer such that $$$c_k$$$ is not a value from the array $$$a$$$. Obviously, $$$k$$$ is not saturated. Since the number of operations of the first type covering some integer decreases only when we have to close them, it always decreases to some number in $$$a$$$, so it is impossible that $$$c_{k - 1} > c_k$$$. It is also impossible that $$$c_{k - 1} = c_k$$$, since $$$k$$$ is the minimum integer such that $$$c_k$$$ does not belong to array $$$a$$$. So, $$$c_{k - 1} < c_k$$$, it means that some number of operations of the first type started in integer $$$k$$$. We can either get rid of them altogether (if they end in $$$k$$$ as well), or shift them to $$$k + 1$$$, so $$$c_k$$$ belongs to the array $$$a$$$. That way, if in the optimal answer some value $$$c_k$$$ does not belong to $$$a$$$, we can reconstruct it so it is no longer the case.
The proof ends here
Overall, since we have only up $$$n$$$ disctict values of $$$j$$$, the solution runs in $$$O(n^2)$$$ (though it is possible to solve the problem faster).