Benzina

Subtask 1

Se considera toate parantezarile corecte si se alege cea cu cost maxim.

Subtask 2 -

Varianta 1:

dp[st][dr] - costul maxim daca fixam intervalul [st;dr]
Ne bazam pe definitia unui sir corect parantezat
sir='('sir_mic')'
sau sir=sir_mic1+sir_mic2, unde + este concatenarea
Obtinem recurenta
dp[st][dr]=max(dp[st+1][dr-1]+a[st]+b[dr],{dp[st][k]+dp[k+1][dr], unde k este de la st+1 la dr-1})
Raspunsul se afla in dp¹[2*n].

Varianta 2

dp[i][j][k] - valoarea maxima daca ajungem la pozitia i cu j paranteze deschise si k inchise, intotdeauna k ≤ j.
dp[i][j][k] se poate propaga in dp[i][j+1][k] sau in dp[i][j][k+1], daca k<j.
Raspunsul se afla in dp[2*n][n][n]

Subtask 3 -

Tinem un sir fictiv, in care pentru fiecare '(' punem +1,iar pentru ')' punem -1.
Observam ca un ce are toate sumele partiale mai mari sau egale cu 0 si are ultima suma partiala 0 satisface conditia de parantezare corecta.
Tinem dp[i][j] = valoarea maxima daca ajungem pana la pozitia i, cu suma partiala j, j intotdeauna mai mare sau egal cu 0.
dp[i][j] se propaga in dp[i+1][j+1] si in dp[i+1][j-1] (daca j>0).
Raspunsul se afla in dp[2*n][ 0 ].

Subtask 4 -

Consideram ca tot sirul este format din paranteze inchise ')' si vrem sa punem N paranteze deschise '(', astfel incat parantezarea sa fie corecta si sa maximizam costul (a[i] - b[i]) pentru parantezele deschise pe care le punem.

Pentru a face parantezarea corecta, vom pune a i-a paranteza deschisa intre primele (2 * i - 1) paranteze.
Demonstratie: Consideram ca paranteza deschisa are costul 1, iar paranteza inchisa are costul -1. Vrem ca fiecare prefix sa aibe suma costurilor pozitiva, deci pentru un prefix de lungime (2 * i - 1), vrem ca cel putin i paranteze sa fie deschise.

Pentru a maximiza costul, vom lua pentru fiecare prefix de lungime impara valoare maxima (a[j] - b[j]) , j <= 2 * i - 1, pe care nu am pus deja o paranteza deschisa. Aceasta operatie se poate efectua usor cu ajutorul unui maxheap.

Observatie: Sunt cunoscute inca 3 solutii de 100 de puncte.