Diferente pentru moisil-2015/naveplanare intre reviziile #8 si #12

Nu exista diferente intre titluri.

Diferente intre continut:

În continuare avem de rezolvat următoarea problema: având un vector V sortat, să se determine numărul minim de operaţii necesare astfel încât să avem minim K valori distincte în el. O operaţie înseamna creşterea/scăderea cu 1 a oricărui element din vector.
Vom folosi următoarea dinamică:
DP(i, j, k) = numărul minim de operaţii necesare pentru a avea exact j poziţii distincte formate din primele i numere, iar numarul de pe poziţia i are orice valoare din intervalul [-inf, k]
DP(i, j, k) = min(
     ● DP(i-1, j-1, k-1) + abs(V[i] - j), “Vom creste numarul de elemente distincte cu 1, deci va trebui sa ducem elementul v[i] la valoarea j”
     ● min(DP(i-1, j, k), DP(i, j, k-1))
@DP(i, j, k)@ = numărul minim de operaţii necesare pentru a avea exact j poziţii distincte formate din primele i numere, iar numarul de pe poziţia i are orice valoare din intervalul @[-inf, k]@
@DP(i, j, k)@ = @min(@@DP(i-1, j-1, k-1) + abs(V[i] - k)@, “Vom creste numarul de elemente distincte cu 1, deci va trebui sa ducem elementul v[i] la valoarea k”
     ● @min(DP(i-1, j, k), DP(i, j, k-1))@
);
Solutia va fi minimul dintre toate DP(N, K..N, 0..max(v)+size(v)))
Solutia va fi minimul dintre toate @DP (N, K..N, 0..max(v) + size(v)))@
Răspunsul la problema va fi suma acestor doua minime (pentru X şi pentru Y).
Complexitate: O(N*N*K)
Complexitate: @O(N*N*K)@
 
O altă soluţie care obtine 100 de puncte se poate implementa cu flux.

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.