infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: David Gergely din Iunie 20, 2015, 14:21:18

Titlul: Hint la problema cu Dinamica!
Scris de: David Gergely din Iunie 20, 2015, 14:21:18

Avem o matrice N*N. Trebuie sa alegem un sir care are suma maxima cu urmatoarele conditi: pornim de pe prima coloana-> putem merge in fata, fata sus, fata jos. De pe fiecare coloana trebuei sa avem doar un singur element!
ex:

Cod:

4
2 -3 4 -1
-4 -2 15 -7
12 -6 -9 7
3 6 2 5

Daca ma puteti ajuta cu un hint! Am incercat eu cu DP dar nu mi-a iesit!
Multumesc!

Titlul: Răspuns: Hint la problema cu Dinamica!
Scris de: Vintur Cristian din Iunie 24, 2015, 17:05:38

Construiesti o matrice best[ i ][ j ] - suma maxima a unui sir care se termina pe pozitia (i, j)

Cod:

best[i][1] = a[i][1] (prima coloana)

best[i][j] = a[i][j] + max(best[i-1][j-1], best[i][j-1], best[i+1][j-1])

parcurgerea se face pe coloane, nu pe linii

raspunsul este maximul dintre best[ i ][ n ], 1<=i<=n

pentru reconstituire trebuie o matrice auxiliara, pred[ i ][ j ] care retine linia elementului precedent celui de pe pozitia (i, j)

Titlul: Răspuns: Hint la problema cu Dinamica!
Scris de: David Gergely din Iunie 26, 2015, 20:22:59

Multumesc! Am rezolvat problema! Eu greseam la initializarea primei coloane! Si atunci nici recurenta nu era corecta! :D :D