Nu aveti permisiuni pentru a descarca fisierul grader_test10.in
Diferente pentru moisil-2015/naveplanare intre reviziile #3 si #12
Nu exista diferente intre titluri.
Diferente intre continut:
Scrie aici despre moisil-2015/naveplanare Nu putem vedea macar solutiile? Nu sunt sigur ca aveam acces sa scriu aici...
h2(#Naveplanare). 'Naveplanare':problema/naveplanare Autor: stud. Cosmin Tututnaru, Universitatea „Babeş-Bolyai”, Cluj-Napoca Descrierea soluţiei (Cosmin Tutunaru) Soluţie – 100 pct Putem descompune problema pe OX şi OY, având în vedere că mişcările sunt independente. În acest fel putem sorta separat toate valorile X şi toate valorile Y. Î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] - 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)))@ Răspunsul la problema va fi suma acestor doua minime (pentru X şi pentru Y). Complexitate: @O(N*N*K)@ O altă soluţie care obtine 100 de puncte se poate implementa cu flux.