# PBinfo #1755 – Democratie – Rezolvare C++

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

## Enunț

Arpsod are în curtea sa N copaci foarte bătrâni, așezați în linie și numerotați de la 1 la N. Fiecare copac are o înălțime cunoscută, Hi. Există riscul ca la un vânt mai puternic aceștia să cadă, provocând stricăciuni.

Astfel Arpsod a angajat doi muncitori pentru a-i tăia copacii. Primul muncitor va începe să taie copacii în ordinea 1, 2, 3, ... ,N iar cel de-al doilea în ordinea N, N-1, N-2, ... 1.

Fiind un tărâm democratic, fiecare muncitor dorește să fie plătit pentru fiecare metru pe care îl taie. Muncitorul 1 are un tarif de T1 pe metru iar muncitorul 2 un tarif de T2 pe metru. Dacă un muncitor a început să taie un copac, acesta îl va tăia integral. Din motive de protecție a muncii, muncitorilor nu le este permis să lucreze simultan. De aici apare următoarea pretenție: dacă după tăierea unui copac, muncitorul nu este înlocuit de colegul său, acesta va cere un cost suplimentar C pentru a rămâne să taie în continuare.

De exemplu, dacă avem 3 copaci: 1, 2, 3 și muncitorul 1 taie singur toți copacii, acesta va cere un cost suplimentar de 2 ori (pentru copacul 2 și copacul 3).

Cerința
Arpsod vă cere să determinați costul minim pe care îl poate plăti astfel încât toți cei N copaci să fie tăiați.

Date de intrare
Pe prima linie a fișierului democratie.in se va afla numărul natural N, reprezentând numărul de copaci. 
Pe cea de-a doua linie vor exista N numere naturale nenule reprezentând înălțimile celor N copaci.
Pe cea de-a treia linie se vor afla două numere naturale T1 și T2 reprezentând tariful pe metru al muncitorului 1 respectiv al muncitorului 2.
Pe ultima linie se vor afla două numere naturale C1 și C2 reprezentând costul suplimentar cerut de muncitorul 1 respectiv muncitorul 2.

Date de ieșire
În fișierul democratie.out se va scrie, pe prima și singura linie din fișier, costul minim pe care Arpsod trebuie să-l plătească.

Restricții și precizări

1 ≤ N ≤ 100.000
1 ≤ T1, T2 ≤ 100
1 ≤ C1, C2 ≤ 10.000
1 ≤ Hi ≤ 100
Se garantează că pentru 20% din teste 1 ≤ N ≤ 10
Costul suplimentar este același indiferent de înălțimea copacului ce va fi tăiat.
Este posibil ca un muncitor să taie singur toți copacii.
Un muncitor va tăia complet un copac.
Cam scumpă democrația asta!

Exemplu:
democratie.in

4
1 2 3 4
7 2
3 9
democratie.out

34
Explicație
Ordinea muncitorilor:
M2 -> M1 -> M2 -> M2
Costul: (2*4) + (7*1) + (2*3) + (2*2 + 9)

## Cod sursă C++

```cpp
// implementare: Cristi Dospra
// punctaj: 20p
// complexitate: O(2^N * N )
#include <fstream>
using namespace std;
#define Nmax 100002
#define inf 2000000000
ifstream fin ( "democratie.in" );
ofstream fout ( "democratie.out" );
int N, T1, T2, C1, C2;
int v[Nmax], Sol = inf;
int config[Nmax];
void bkt ( int poz ){
    if ( poz > N ){
        int st = 1, dr = N;
        int Total = 0;
        for ( int i = 1; i <= N; ++i ){
            if ( config[i] == 1 ){
                Total += v[st] * T1;
                st++;
                if ( config[i-1] == config[i] )
                    Total += C1;
            }
            else{
                Total += v[dr] * T2;
                dr--;
                if ( config[i-1] == config[i] )
                    Total += C2;
            }
        }
        Sol = min ( Sol, Total );
        return ;
    }
    for ( int i = 1; i <= 2; ++i ){
        config[poz] = i;
        bkt ( poz + 1 );
    }
}
int main(){
    fin >> N;
    for ( int i = 1; i <= N; ++i )
        fin >> v[i];
    fin >> T1 >> T2 >> C1 >> C2;
    bkt ( 1 );
    fout << Sol;
    return 0;
}
```

## Resurse

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