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:

• cmin[i][j][0] = costul minim pentru a amplasa in total i depozite in benzinariile [1..j], iar al i-lea depozit se afla localizat chiar in benzinaria j
• cmin[i][j][1] = costul minim pentru a amplasa in total i depozite in benzinariile [1..j iar al i-lea depozit nu este neaparat amplasat in benzinaria j

Relatiile de recurenta sunt urmatoarele:

• cmin[i][j][0] = min _{0 ≤ k < j}@( cmin[i-1][k]¹ + suma@ _{k < p ≤ j} (c[p]*(d[j]-d[p])))
• @cmin[i][j]¹ = @