== include(page="template/taskheader" task_id="redu") ==
Rebeca are un sir de caractere $S$ de lungime $N$ para, ce contine litere mici ale alfabetului englez. Rebeca poate efectua asupra sirului oricate operatii de reducere. O operatie de reducere consta in alegerea a doua caractere $x$ si $y$ **consecutive** (adica apar unul dupa celalat) si eliminarea lor din sir; cele doua siruri posibil ramase se lipesc la loc. Fiecare operatie are un cost ce depinde de perechea ($x$, $y$) aleasa, determinat de matricea $C$ cu $26$ de linii si $26$ de coloane unde $C[ x ][ y ]$ este egal cu costul eliminarii perechii ($x$, $y$).
Rebeca are un sir de caractere $S$ de lungime $N$ para, ce contine litere mici ale alfabetului englez. Rebeca poate efectua asupra sirului oricate operatii de reducere. O operatie de reducere consta in alegerea a doua caractere $x$ si $y$ **consecutive** (adica apar unul dupa celalat) si eliminarea lor din sir; cele doua siruri posibil ramase se lipesc la loc. Fiecare operatie are un cost ce depinde de perechea ( $x$, $y$ ) aleasa, determinat de matricea $C$ cu $26$ de linii si $26$ de coloane unde $C[x][y]$ este egal cu costul eliminarii perechii ( $x$, $y$ ). Rebeca vrea sa reduca tot sirul cu un cost total cat mai mic.
h2. Date de intrare
Fişierul de intrare $redu.in$ ...
Fisierul de intrare $redu.in$ va contine pe prima linie numarul $N$ reprezentand lungimea sirului $S$. A doua linie va contine sirul $S$. Urmatoarele $26$ de linii vor contine cate $26$ de numere separate prin spatii reprezentand matricea $C$. A $i$-a linie si a $j$-a coloana reprezinta costul unei operatii ( $x$, $y$ ) unde $x$ este a $i$-a litera mica din alfabetul englez iar $y$ este a $j$-a litera mica din alfabetul englez.
h2. Date de ieşire
În fişierul de ieşire $redu.out$ ...
In fisierul de iesire $redu.out$ veti afisa un sigur numar reprezentand costul total minim cu care Rebeca poate reduce intreg sirul $S$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 500$
* $N$ este par
* $0 ≤ C[i][j] ≤ 10 000$
h2. Exemplu
table(example). |_. redu.in |_. redu.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
acab
4 2 3 5 9 1 6 9 2 4 1 3 7 8 8 4 7 3 9 6 3 4 5 6 3 9
1 5 0 3 7 7 9 9 4 0 2 1 0 4 5 1 9 4 2 8 8 1 3 8 7 7
1 4 5 6 3 8 3 6 1 0 5 1 9 9 1 2 0 3 8 6 5 8 0 9 6 1
0 1 9 0 0 1 6 5 9 0 4 3 8 7 5 3 0 7 2 4 1 5 7 9 3 2
7 5 3 5 6 6 7 5 8 7 9 4 3 0 6 9 3 4 6 9 9 7 8 4 1 9
9 8 8 2 3 6 7 8 3 6 4 0 1 2 0 2 9 5 3 5 4 8 2 2 9 1
9 7 5 2 6 6 1 5 0 6 3 0 4 8 6 1 1 9 5 1 2 4 8 7 0 4
5 2 6 5 5 8 2 3 0 1 9 3 8 0 9 1 2 6 1 8 9 2 9 4 3 1
9 1 8 1 5 6 3 4 1 0 2 5 3 2 6 3 8 4 5 9 7 7 7 9 7 6
1 6 1 7 0 2 0 0 3 8 6 8 2 9 8 6 7 2 0 3 7 8 0 4 8 9
3 5 0 0 4 4 8 5 3 0 9 3 1 2 1 9 2 5 9 0 1 6 4 2 1 1
2 3 7 2 5 0 0 5 2 4 1 1 9 4 1 8 8 4 2 1 4 4 9 5 6 2
3 1 6 6 4 9 2 2 1 7 4 1 4 7 7 6 8 8 0 1 8 0 8 0 4 2
6 3 9 3 7 2 6 4 0 2 3 2 6 6 1 1 0 6 8 7 4 8 6 6 1 4
7 9 7 3 1 5 6 2 8 3 6 6 9 7 9 2 1 5 1 3 8 1 9 6 0 3
6 8 9 8 5 8 7 2 1 1 7 9 5 8 5 2 6 4 9 5 9 0 3 0 5 1
3 6 0 5 9 6 4 1 6 9 1 6 3 5 7 2 4 2 2 1 6 9 6 5 6 7
8 1 9 5 3 2 2 5 7 3 3 1 4 0 2 8 8 7 3 5 0 9 9 2 3 8
3 1 3 0 8 3 1 7 9 6 9 3 3 8 6 7 2 3 9 4 1 7 2 6 4 4
7 5 8 0 3 2 1 9 4 9 4 5 6 5 4 7 8 7 8 5 6 0 8 5 6 1
4 0 7 0 4 4 6 3 5 1 7 6 0 1 8 5 8 6 0 2 4 1 2 4 6 8
4 6 6 0 7 2 3 4 3 7 0 1 2 5 2 9 4 5 2 2 0 1 8 2 5 4
3 9 8 1 0 4 7 8 7 4 0 0 0 5 7 1 6 2 8 1 3 2 6 6 6 8
9 7 0 6 1 6 6 2 9 6 6 7 4 3 3 6 3 4 2 3 7 0 7 5 1 0
0 7 8 6 5 9 3 8 6 7 6 4 9 5 0 7 4 6 1 8 2 6 4 4 1 3
7 8 0 8 1 0 6 1 9 3 1 2 1 9 1 7 3 2 3 5 0 9 1 3 9 5
| 3
|
h3. Explicaţie
...
Rebeca va efectua operatia $a **c a** b$ cu costul $C[ 3 ][ 1 ] = 1$, iar sirul ramas va fi $ab$. Apoi va efectua operatia $**a b**$ cu costul $C[ 1 ][ 2 ] = 2$, pentru a reduce tot sirul. Costul total este egal cu $3$.
== include(page="template/taskfooter" task_id="redu") ==
