Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-09-24 14:18:02.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Solutii runda 2
Curcubeu
Trompeta
Problema se rezolva cu metoda greedy. Se formeaza treptat rezultatul cu ajutorul unei stive: daca cifra curenta este mai buna decat cea din varful stivei si numarul de cifre din stiva + numarul de cifre ramase ≥ M, atunci elementul din varful stivei este eliminat. Acest algoritm are complexitate O(N).
MMsir
Rompetrol
Vom calcula costurile cmin[i][j][0]
si cmin[i][j]1, avand semnificatiile: