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] + 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]]).

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]]).

h2. "Negot":https://infoarena.ro/problema/negot