| Fişierul intrare/ieşire: | redu.in, redu.out | Sursă | Algoritmiada 2010, Runda 2 |
| Autor | Cosmin Gheorghe | Adăugată de |  Gheorghe Cosmin •gcosmin |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 vrea sa reduca tot sirul cu un cost total cat mai mic.
Date de intrare
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.
Date de ieşire
In fisierul de iesire redu.out veti afisa un sigur numar reprezentand costul total minim cu care Rebeca poate reduce intreg sirul S.
Restricţii
- 1 ≤ N ≤ 500
- N este par
- 0 ≤ C[i][j] ≤ 10 000
Exemplu
| redu.in | redu.out |
|---|---|
| 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 |
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.
