Revizia anterioară Revizia următoare
Negustori
Vom rezolva problema folosind metoda programării dinamice. Iară. :)
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 repartizaţi la locaţia 1, 0 sau mai mulţi 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 locurilor k, .., n cu negustori rămânând m locuri libere.
Fie dp[k][m] 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[i] numărul de negustori locali care preferă locaţia i, cl[i] numărul de negustori locali care preferă una din locaţiile între 1 şi i (cl[i] = l[1] + .. + l[i]). Pentru a calcula dp[k][m], ne rămâne să repartizăm negustori străini pe locul k pe lângă cei l[k] negustori locali. Această repartizare se realizează în limita locurilor disponibile. Numărul locurilor disponibile este egal cu ld[k][m] = m+1-l[k] (cele m locuri libere la care adăugăm locul k şi scădem pe cele ocupate de negustorii locali). 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+1, .., n şi pe cei locali repartizaţi pe locaţiile 1, .., k, adică ns[k][m] = n-(n-k-m)-cl[k]. Astfel, numărul total de negustori străini este ns[k][m] = m+k-cl[k]. Rezultă că vom alege i negustori străini din cei ns[k][m] pe care îi vom repartiza pe poziţia k. Astfel, recurenţa este: ![dp[k][m] = \displaystyle\sum_{i=0}^{ld[k][m]} \dbinom{ns[k][m]}{ld[k][m]-i} * dp[k-1][i]](https://www.infoarena.ro/static/images/latex/123084f309cd9274b32624f55095d4c3_13.79865pt.gif "dp[k][m] = \displaystyle\sum_{i=0}^{ld[k][m]} \dbinom{ns[k][m]}{ld[k][m]-i} * dp[k-1][i]")
. Avem dp[1][i] = 1, oricare i ≥ 0. Rezultatul se găseşte în dp[n][0].
Complexitatea soluţiei: O(n3). Voi îmbunătăţi claritatea soluţiei curând. :)
