Nu aveti permisiuni pentru a descarca fisierul grader_test5.in
Diferente pentru problema/palsubsecv intre reviziile #9 si #13
Diferente intre titluri:
palsubsecv
Palsubsecv
Diferente intre continut:
== include(page="template/taskheader" task_id="palsubsecv") ==
Se da un sir de caractere $S$ de lungime $N$. Trebuie sa gasim subsirul palindromic al lui $S$ de lungime maxima, cu lungime para. Avem un buget de $B$ dolarei. Odata ce alegem o solutie, va trebui sa tinem cont de $R$ restrictii care ne vor scadea din buget.
Se da un sir de caractere $S$ de lungime $N$. Trebuie sa gasim subsirul palindromic al lui $S$ de lungime maxima, cu lungime para. De asemenea avem un buget de $B$ dolarei. Odata ce alegem o solutie, va trebui sa tinem cont de $R$ restrictii care ne vor scadea din buget.
O restrictie de forma $(a, b, c)$ inseamna ca daca este luata subsecventa dintre $a$ si $b$ in palindrom, trebuie sa platim $c$ dolarei. Asta inseamna ca, fiind alese *toate* pozitiile dintre $a$ si $b$ in palindromul solutie, trebuie sa platim $c$ dolarei. Care este palindromul par de lungime maxima astfel incat la final sa ramanem cu un numar nenegativ de dolarei?
h2. Restricţii
* $1 ≤ T ≤15$
* $1 ≤ T ≤ 20$
* $1 ≤ N ≤ 33$ * $1 ≤ R ≤ 5.000$ * $1 ≤ B ≤ 10^9^$
* $1 ≤ c ≤ 10^5^$ * $S$ contine doar litere mici ale alfabetului englez * $x$ e nenegativ daca $x ≥ 0$
* *Atentie!* Trebuie sa alegeti un subsir al sirului, nu o subsecventa! Costul este calculat in functie de subsecvente
* *Atentie!* Trebuie sa alegeti un subsir al sirului, nu o subsecventa! Doar costul este calculat in functie de subsecvente * Va recomandam ca daca tineti in mana stanga dolarei, in mana dreapta sa aveti leii grei.
h2. Exemplu
