804 Trmax

[•wefgef]

Aici puteti discuta despre problema Trmax.

[•valytgjiu91]

nu inteleg ce nu imi iese la problema asta
care ma poate ajuta si pe mine pe urmatorul exemplu:
5 8 5
1 1
1 3
2 5
3 8
5 2

mie imi da 9

[•anna_bozianu]

Raspunsul 9 este corect. Tu ai de 4 ori TLE si de 3 ori incorect. Incearca sa detaliezi. Cam ce metoda de rezolvare incerci? 

[•ctlin04]

poate sa-mi sugereze careva vreo optimizare la problema asta, ca tot iau 60 puncte cu TLE pe restul, si fac prin programare dinamica, ca in solutia oficiala, dar oricum nu intra in timp. Poate sa fie de la asta ca eu lucrez in fpc?

[•justsomedude]

Poate au avut sau vor mai avea si altii problema optimizarii, desi e destul de standard. In rezolvare se folosesc 2 matrice, iar din recurentele termenilor generali ai matricelor reiese clar ca un element A[j] depinde doar de A[j-1], deci n-are rost sa retin efectiv o matrice, ce doar un vector A[], pe care sa-l completez de fiecare data cand parcurg o linie.
Dar cea mai importanta optimizare ar fi in cadrul matricei best[][] care imi ofera si solutia. best[j] nu depinde decat de best[i-1][j-1] si de A[j], ceea ce inseamna ca, de fapt, este nevoie de retinerea doar a 2 linii din matrice, caci pe a doua o completez cu ajutorul primei.

Mai ramane de facut interschimbarea liniilor, dar n-are rost sa o copiez integral pe a doua in prima, ci, daca notam L0 prima linie cu care lucram si cu L1 a doua linie, matricea best[n][m] se reduce la best[2][m], iar L0 = 0 si L1 = 1 (initial).
Functia care imi permite "interschimbarea" celor 2 linii este f(x) = 1 - x (din 1 imi face 0 si din 0 face 1). Dupa fiecare parcurgerea a unei linii imi voi interschimba liniile la modul L0 = 1 - L0 si L1 = 1 - L1. Sper ca v-am fost de ajutor!