#1755
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
).
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.
Concursul EMPOWERSOFT, 2016
ID | Utilizator | Problema | Data încărcării | Stare | ||
---|---|---|---|---|---|---|
Democratie | 09 Ianuarie 2019, 16:26 | Evaluare finalizată | 90 | |||
Democratie | 09 Ianuarie 2019, 16:24 | Evaluare finalizată | 5 | |||
Democratie | 09 Ianuarie 2019, 16:24 | Evaluare finalizată | 95 | |||
Democratie | 09 Ianuarie 2019, 16:23 | Evaluare finalizată | 95 | |||
Democratie | 07 Ianuarie 2019, 17:08 | Evaluare finalizată | E.C | |||
Democratie | 06 Ianuarie 2019, 16:49 | Evaluare finalizată | 0 | |||
Democratie | 06 Ianuarie 2019, 16:16 | Evaluare finalizată | E.C | |||
Democratie | 05 Ianuarie 2019, 19:27 | Evaluare finalizată | 50 | |||
Democratie | 02 Decembrie 2018, 18:20 | Evaluare finalizată | 100 | |||
Democratie | 02 Decembrie 2018, 18:18 | Evaluare finalizată | 20 | |||
Democratie | 16 Noiembrie 2018, 09:35 | Evaluare finalizată | 100 | |||
Democratie | 02 Noiembrie 2018, 21:19 | Evaluare finalizată | 100 | |||
Democratie | 29 Septembrie 2018, 23:21 | Evaluare finalizată | 100 | |||
Democratie | 11 Septembrie 2018, 20:29 | Evaluare finalizată | 100 | |||
Democratie | 11 Septembrie 2018, 20:27 | Evaluare finalizată | 100 | |||
Democratie | 11 Septembrie 2018, 20:23 | Evaluare finalizată | 100 | |||
Democratie | 11 Septembrie 2018, 20:23 | Evaluare finalizată | 55 | |||
Democratie | 11 Septembrie 2018, 20:18 | Evaluare finalizată | 100 | |||
Democratie | 17 August 2018, 14:06 | Evaluare finalizată | 100 | |||
Democratie | 28 Mai 2018, 20:00 | Evaluare finalizată | 0 | |||
Democratie | 04 Mai 2018, 16:28 | Evaluare finalizată | 50 | |||
Democratie | 04 Mai 2018, 16:11 | Evaluare finalizată | 25 | |||
Democratie | 03 Mai 2018, 23:26 | Evaluare finalizată | 100 | |||
Democratie | 03 Mai 2018, 23:13 | Evaluare finalizată | 95 | |||
Democratie | 03 Mai 2018, 18:55 | Evaluare finalizată | 100 | |||
Democratie | 01 Mai 2018, 22:17 | Evaluare finalizată | 40 | |||
Democratie | 30 Aprilie 2018, 12:40 | Evaluare finalizată | 100 | |||
Democratie | 30 Aprilie 2018, 10:22 | Evaluare finalizată | 100 | |||
Democratie | 24 Ianuarie 2018, 10:08 | Evaluare finalizată | 100 | |||
Democratie | 10 Decembrie 2017, 19:16 | Evaluare finalizată | 100 | |||
Democratie | 26 Iulie 2017, 13:49 | Evaluare finalizată | 100 | |||
Democratie | 21 Mai 2017, 12:48 | Evaluare finalizată | 100 | |||
Democratie | 17 Aprilie 2017, 20:34 | Evaluare finalizată | 100 | |||
Democratie | 14 Aprilie 2017, 21:32 | Evaluare finalizată | 100 | |||
Democratie | 14 Aprilie 2017, 21:23 | Evaluare finalizată | 100 | |||
Democratie | 14 Aprilie 2017, 21:19 | Evaluare finalizată | 5 | |||
Democratie | 14 Aprilie 2017, 21:04 | Evaluare finalizată | 95 | |||
Democratie | 23 Martie 2017, 21:59 | Evaluare finalizată | 100 | |||
Democratie | 23 Martie 2017, 21:50 | Evaluare finalizată | 30 | |||
Democratie | 23 Martie 2017, 20:35 | Evaluare finalizată | 95 | |||
Democratie | 23 Martie 2017, 20:34 | Evaluare finalizată | 90 | |||
Democratie | 23 Martie 2017, 20:33 | Evaluare finalizată | 95 | |||
Democratie | 21 Martie 2017, 19:53 | Evaluare finalizată | 100 | |||
Democratie | 21 Martie 2017, 19:41 | Evaluare finalizată | 50 | |||
Democratie | 20 Martie 2017, 17:09 | Evaluare finalizată | 100 | |||
Democratie | 15 Martie 2017, 19:47 | Evaluare finalizată | 100 | |||
Democratie | 13 Martie 2017, 18:48 | Evaluare finalizată | E.C | |||
Democratie | 13 Martie 2017, 18:39 | Evaluare finalizată | 55 | |||
Democratie | 13 Martie 2017, 18:36 | Evaluare finalizată | 65 | |||
Democratie | 13 Martie 2017, 18:28 | Evaluare finalizată | 20 |