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 1.000.000
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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Vraja2:

#include <iostream>
using namespace std;

int n , v[1005], cnt;

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

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

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #839 Vraja2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #839 Vraja2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #839 Vraja2