Enunț
În atelierul de vitralii, un meșter trebuie să unească mai multe benzi de sticlă așezate într-o ordine fixă. Nu le poate rearanja. La fiecare pas, lipește două grupuri vecine și obține un grup cu lungimea egală cu suma lungimilor lor. Cuptorul consumă energie egală cu această nouă lungime, chiar dacă unele benzi au mai fost încălzite la pașii anteriori.
Cerință
Determină energia totală minimă pentru a obține un singur grup. Costurile tuturor lipirilor se adună. La fiecare pas se unesc exact două grupuri vecine în ordinea curentă.
Date de intrare
Se citește n, apoi cele n lungimi ale benzilor, de la stânga la dreapta.
Date de ieșire
Afișează un singur număr întreg: costul total minim al lipirilor. Dacă există deja o singură bandă, răspunsul este 0.
Restricții
1 ≤ n ≤ 8; 1 ≤ fiecare lungime ≤ 10. Ordinea inițială nu se poate schimba.
Explicație
Pentru 2,1,4,2,3, o succesiune optimă este: unim 2 și 1, cu cost 3; unim ultimele 2 și 3, cu cost 5; unim grupul 3 cu banda 4, cu cost 7; unim grupurile 7 și 5, cu cost 12. Totalul este 3+5+7+12=27. În al doilea exemplu nu este necesară nicio lipire.
Observații
Selecție Algo25 pentru pregătirea interviurilor: programare dinamică.
Reper tematic pentru pregătire: https://www.hackerrank.com/interview/interview-preparation-kit
Exemple
2 EXEMPLEExemplul 1
Exemplul 1, reprezentat vizual. Numărul de sub o casetă este poziția, nu valoarea. Valorile egale de pe poziții diferite rămân elemente distincte ale șirului.Mărește schema ↗Date de intrare
5
2 1 4 2 3
Date de ieșire
27
Exemplul 2
Date de intrare
1
1
Date de ieșire
0
Ai nevoie de un indiciu?
Descoperă doar cât îți trebuie. Indiciile nu scad punctajul.
Trimite o soluție
Se verifică autentificarea…
Deschide atelierul cu sugestii și teste locale în 4 limbaje →