h2. "Sunmihai":https://infoarena.ro/problema/sunmihai
Acesta problema se rezolva cu metoda programarii dinamice. Vom calcula dp[i][j] - costul minim pentru a avea pe ultima piesa din domino valoarea din dreapta j, trecand prin primele i domino-uri date. Vom folosi notatia: v1[i] - valoarea din stanga a celui de-al i-lea domino dat initial si v2[i] - valoarea din dreapta. Dp[ 1 ][v2[ 1 ]] este 0 pentru ca nu aplicam nicio operatie primului domino, iar dp[ 1 ][v1[ 1 ]] este maxim A (v1[i] poate fi egal cu v2[i]), pentru ca intoarcem domino-ul; restul tabloului de dinamica il vom initializa cu o valoare mare. Ajunsi la a i-a piesa putem sa abordam in urmatorul fel: vrem sa o pastram exact cum e, iar dp[i][v2[i]] va fi dp[i-1][v1[i]]; vrem sa o intoarcem, iar dp[i][v1[i]] va fi dp[i-1][v2[i]] + A (atentie cand v1[i]=v2[i]), o scoatem cu cost B, iar dp[i][j] va fi egal cu dp[i-1][j] sau adaugam o piesa cu cost C. Piesa de tip C are sens sa fie adaugata doar cand vrem sa pastram a i-a piesa si nu avem anterior o piesa de care sa o legam, adica dp[i-1][v1[i] / v2[i]] este valoarea aceea mare cu care am initializat tabloul. Putand insera o piesa cu orice valori v1 si v2, nu ne intereseaza care sunt acestea si vom insera piesa dupa o configuratie dp[i-1][j], nu conteaza cine este j (de la 1 la 100), cu dp valoarea minima. Dp[i][v2[i]] va fi dp[i-1][j] (minim) + C. Raspunsul se va afla in min(dp[n][v1[i]], dp[n][v2[i]]).
Acesta problema se rezolva cu metoda programarii dinamice. Vom calcula dp[i][j] - costul minim pentru a avea pe ultima piesa din domino valoarea din dreapta j, trecand prin primele i domino-uri date. Vom folosi notatia: v1[i] - valoarea din stanga a celui de-al i-lea domino dat initial si v2[i] - valoarea din dreapta. Dp[ 1 ][v2[ 1 ]] este 0 pentru ca nu aplicam nicio operatie primului domino, iar dp[ 1 ][v1[ 1 ]] este maxim A (v1[i] poate fi egal cu v2[i]), pentru ca intoarcem domino-ul; restul tabloului de dinamica il vom initializa cu o valoare mare. Ajunsi la a i-a piesa putem sa abordam in urmatorul fel: vrem sa o pastram exact cum e, iar dp[i][v2[i]] va fi dp[i-1][v1[i]]; vrem sa o intoarcem, iar dp[i][v1[i]] va fi dp[i-1][v2[i]] + A (atentie cand v1[i]=v2[i]), o scoatem cu cost B, iar dp[i][j] va fi egal cu dp[i-1][j] + B sau adaugam o piesa cu cost C. Piesa de tip C are sens sa fie adaugata doar cand vrem sa pastram a i-a piesa si nu avem anterior o piesa de care sa o legam, adica dp[i-1][v1[i] / v2[i]] este valoarea aceea mare cu care am initializat tabloul. Putand insera o piesa cu orice valori v1 si v2, nu ne intereseaza care sunt acestea si vom insera piesa dupa o configuratie dp[i-1][j], nu conteaza cine este j (de la 1 la 100), cu dp valoarea minima. Dp[i][v2[i]] va fi dp[i-1][j] (minim) + C. Raspunsul se va afla in min(dp[n][v1[i]], dp[n][v2[i]]).
h2. "Negot":https://infoarena.ro/problema/negot
Aceasta este o aplicatie de flux maxim, insa exista o solutie care se misca mai bine folosind cuplaj maxim in graf bipartit.
Pentru flux: vom crea un nod 0 sursa si vom crea N muchii de capacitate K. Toate muchiile de la producator la magazin au capacitate 1. Vom crea, de altfel, si un nod destinatie si M muchii de capacitate 1 de la magazine la destinatie.
Pentru flux: vom crea un nod 0 sursa si N muchii de capacitate K de la sursa la producatori. Toate muchiile de la producator la magazin au capacitate 1. Vom crea, de altfel, si un nod destinatie si M muchii de capacitate 1 de la magazine la destinatie.
Pentru cuplaj: putem "clona" un producator de K ori si fiecare clona sa o cuplam cu maxim 1 magazin. Restrictiile permit crearea efectiva a N*K noduri cu tot cu muchiile aferente, insa pentru o solutie performanta vom tine un vector de aparitii al fiecarui nod dintre cele N. Frecventa petru fiecare nod nu trebuie sa fie mai mare decat K in timp ce cuplam.
