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)

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import sys

Nmax = 100002 inf = 2000000000

N, T1, T2, C1, C2 = 0, 0, 0, 0, 0 v = [0] * Nmax Sol = inf config = [0] * Nmax

def bkt(poz):

   global N, T1, T2, C1, C2, Sol, v, config

   if poz > N:
       st, dr = 1, N
       Total = 0

       for i in range(1, N + 1):
           if config[i] == 1:
               Total += v[st] * T1
               st += 1

               if config[i - 1] == config[i]:
                   Total += C1
           else:
               Total += v[dr] * T2
               dr -= 1

               if config[i - 1] == config[i]:
                   Total += C2

       Sol = min(Sol, Total)
       return

   for i in range(1, 3):
       config[poz] = i
       bkt(poz + 1)

def main():

   global N, T1, T2, C1, C2, Sol, v, config

   lines = sys.stdin.readlines()
   N = int(lines[0])

   v = list(map(int, lines[1].split()))

   T1, T2, C1, C2 = map(int, lines[2].split())

   bkt(1)

   print(Sol)

if __name__ == "__main__":

   main()

</syntaxhighlight>