Cerința

De-a lungul bulevardului sunt n copaci, numerotați de la 1 la n, pentru fiecare cunoscându-se înălțimea, exprimată în centimetri. Primarul dorește să taie copacii și apelează la un vrăjitor care va proceda astfel: alege o secvență cât mai lungă de copaci învecinați și aplică o vrajă prin care toți înălțimea tuturor copacilor din secvență scade cu o aceeași valoare, strict pozitivă.

Să se determine care este numărul minim de vrăji care trebuie aplicate astfel încât toți copacii să aibă înălțime zero.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând înălțimile copacilor.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând numărul minim de vrăji necesare.

Restricții și precizări

• 1 ≤ n ≤ 1000
• înălțimile arborilor sunt numere naturale nenule mai mici decât 1000000
• secvența aleasă de vrăjitor la un moment dat nu poate conține copaci de înălțime zero

Exemplu

Intrare

5
5 2 3 5 3

Ieșire

4

Explicație

• prima vrajă se aplică pe întreg șirul de copaci (secvența 1 - 5) și micșorează toți copacii cu 2.
  Șirul devine: 3 0 1 3 1.
• a doua vrajă se aplică pe secvența 1 - 1) și micșorează copacii din secvență cu 3.
  Șirul devine: 0 0 1 3 1.
• a treia vrajă se aplică pe secvența 3 - 5) și micșorează copacii din secvență cu 1.
  Șirul devine: 0 0 0 2 0.
• a patra vrajă se aplică pe secvența 4 - 4) și micșorează copacii din secvență cu 2.
  Șirul devine: 0 0 0 0 0.

#include <bits/stdc++.h>
using namespace std;

int a[1001] , cnt = 0;

void vraja(int st , int dr)
{
    cnt++;
    int min = 10000000;
    for(int i = st ; i <= dr ; ++i)
        if(a[i] < min)
            min = a[i];
    for(int i = st ; i <= dr ; ++i)
        a[i]-=min;
    for(int i = st ; i <= dr ; ++i)
        if(a[i]>0)
        {
            int j = i;
            while(j < dr && a[j+1]>0)
                j++;
            vraja(i , j);
            i=j+1;
        }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        cin >> a[i];
    vraja(1 , n);
    cout << cnt;
    return 0;
}