Rezolvare completă PbInfo #1755 Democratie

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)

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!