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ă, H_i. 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 ≤ H_i ≤ 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

democratie.out

Explicație

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

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 Democratie:

// 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;
}

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 #1755 Democratie

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1755 Democratie 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 #1755 Democratie