Fişierul intrare/ieşire:redu.in, redu.outSursăAlgoritmiada 2010, Runda 2
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inredu.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content