palsubsecv

Palsubsecv

== 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 ≤ N^2^$

* $1 ≤ R ≤ 5.000$

* $1 ≤ B ≤ 10^9^$
* $1 ≤ a ≤ b ≤ N$
* $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! 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

4 5 11
4 2 5
xyyx

3 4 3

3 4 2

2 3 3
|2

2

4

|
h3. Explicaţie
In primul exemplu, ori luam subsirul $aa$ ori $bb$. Nu putem sa le luam pe ambele, deoarece ar trebui sa platim $11$ dolarei din cauza ca luam toate caracterele din intervalul $[4, 5]$.

In al doilea exemplu, luam intregul sir $S$ si platim $2 + 3 = 5$ dolarei.
 

== include(page="template/taskfooter" task_id="palsubsecv") ==