# PBinfo #839 – Vraja2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Marc

## Enunț

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

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.

## Cod sursă C++

```cpp
#include <iostream>
#include <vector>
using namespace std;
class Vraja2 {
public:
  Vraja2();
  void output();
private:
  int m_v[1001];
  int m_n;
  int m_cntv = 0;
  void input();
  void countV();
  void outputDebug();
};
void Vraja2::input() {
  cin >> m_n;
  for (int i = 0; i < m_n; ++i) {
    cin >> m_v[i];
  }
}
Vraja2::Vraja2() {
  input();
  countV();
}
void Vraja2::outputDebug() {
  cout << m_cntv << '\n';
  for (int i = 0; i < m_n; ++i) {
    cout << m_v[i] << ' ';
  }
  cout << "*\n";
}
void Vraja2::countV() {
  bool f = true;
  while (f) {
    f = false;
    for (int i = 0; i < m_n; ++i) {
      if (m_v[i] == 0) continue;
      int j = i, minval = 1000001;
      for (; m_v[j] && j < m_n; ++j)
        minval = min(minval, m_v[j]);
      for (int k = i; k < j; ++k)
        m_v[k] -= minval;
      m_cntv++;
      //outputDebug();
      f = true;
      break;
    }
  }
}
void Vraja2::output() {
  cout << m_cntv;
}
int main() {
  Vraja2 obj;
  obj.output();
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/839)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/839/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-839/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)