Preparando MOJI

Clear the Multiset

2000ms 262144K

Description:

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:

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:

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

Sample Input:

4
1 4 1 1

Sample Output:

2

Sample Input:

5
1 0 1 0 1

Sample Output:

3

Informação

Codeforces

Provedor Codeforces

Código CF1400E

Tags

data structuresdivide and conquerdpgreedy

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 10:05:50

Relacionados

Nada ainda