infoarena informatica de performanta

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 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[1] + .. + l[k]). Pentru a calcula , 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: . Avem . Rezultatul se găseşte în .

Complexitatea soluţiei: O(n³).