summer-challenge-2009/solutii/runda-3/negustori

Soluție Negustori

h2(#negustori). 'Negustori':problema/negustori

:)

Vom rezolva problema folosind metoda programării dinamice.
 
Pornim de la reprezentarea unei modalităţi de repartizare a tuturor celor $n$ negustori la cele $n$ locaţii de pe aleea comercială. O repartizare presupune să avem $0$ sau mai mulţi negustori străini plus cei locali repartizaţi la locaţia $1$, $0$ sau mai mulţi negustori străini plus cei locali la locaţia $2$, etc. Ulterior, negustorii se vor deplasa spre următoarele poziţii spre finalul aleii pentru a găsi un loc liber. Astfel, o stare constă în completarea cu negustori a locurilor $k, .., n$, rămânând $m$ locuri libere pentru completări ulterioare.
 
Fie <tex> dp[k][m] </tex> numărul de repartizări ale negustorilor pe locurile $k, .., n$, rămânând $m$ locuri libere. Vom face următoarele notaţii: $l[k]$ numărul de negustori locali care preferă locaţia $k$, $cl[k]$ numărul de negustori locali care preferă una din locaţiile între 1 şi $k (cl[k] = l[&#49;] + .. + l[k])$. Pentru a calcula <tex> dp[k][m] </tex>, ne rămâne să repartizăm negustori străini pe locul $k-1$ pe lângă cei $l[k-1]$ negustori locali. Această repartizare se realizează în limita locurilor disponibile. Numărul locurilor disponibile este egal cu $locuriLibere = m+1-l[k-1]$ (cele $m$ locuri libere la care adăugăm locul $k-1$ şi scădem pe cele ocupate de negustorii locali, $l[k-1]$). Numărul total de negustori străini rămaşi se obţine scăzând din numărul total de negustori pe cei repartizaţi pe locaţiile $k, .., n$ şi pe cei locali repartizaţi pe una din locaţiile preferate dintre $1, .., k-1$, adică $negustoriStraini = n-(n-k+1-m)-cl[k-1]$. Astfel, numărul total de negustori străini este $m+k-1-cl[k-1]$. Rezultă că vom alege $i$ negustori străini, fără a depăşi numărul locurilor libere, pe care îi vom repartiza pe poziţia $k-1$. Astfel, recurenţa este: <tex> dp[k][m] = \displaystyle\sum_{i=0}^{locuriLibere} \dbinom{negustoriStraini}{locuriLibere-i} * dp[k-1][i] </tex>. Avem <tex> dp[1][i] = 1, \forall i \ge 0 </tex>. Rezultatul se găseşte în <tex> dp[n][0] </tex>.
 
Complexitatea soluţiei: $O(n^3^)$.

private

public