Rezolvare PBinfo #4443

biom – Complex ecologic ce se formează în raport cu un anumit mediu ambiant.

Steve Stonecutter se află într-o lume formată din cuburi, iar fiecare cub aparține unui singur biom. Cuburile sunt dispuse într-o linie și sunt numerotate de la 1 la N. Se consideră că blocurile i și i + 1 sunt vecine între ele pentru toate valorile i de la 1 la N - 1. Putem reprezenta această lume ca și un șir de caractere S de lungime N format din litere mici ale alfabetului limbii engleze, numerotat de la 1 la N, unde al i-lea caracter reprezintă biomul din care face parte al i-lea cub. Pentru a se deplasa, Steve poate face următoarele mișcări:

• se poate deplasa cu costul A de la cubul i la vecinul său imediat la dreapta, adică i + 1;
• se poate deplasa cu costul B de la cubul i la vecinul său imediat la stânga, adică i - 1;
• se poate deplasa cu costul C de la cubul i la cubul j minim pentru care j > i și S[i] = S[j];
• se poate deplasa cu costul D de la cubul i la cubul j maxim pentru care j < i și S[i] = S[j].

Aceste mișcări se pot realiza dacă și numai dacă poziția în care Steve vrea să se deplaseze există. De exemplu, dacă Steve se afla pe cubul 1, acesta nu se poate face a doua sau a patra mișcare.

Cerința

Începând de la cubul 1, Steve dorește să ajungă la cubul N cu cost minim, așa că vă roagă pe voi să aflați care este acest cost.

Date de intrare

În fișierul de intrare biom.in pe prima linie se găsește un singur număr N, reprezentând numărul de cuburi din lumea în care se află Steve. Pe a doua linie se află patru numere A, B, C și D reprezentând costurile fiecărei operații pe care o poate face Steve. Pe a treia linie se află șirul de caractere S de lungime N ce reprezintă harta biomurilor lumii.

Date de ieșire

În fișierul de ieșire biom.out se va afla un singur număr ce reprezintă costul minim de a ajunge de la cubul 1 la cubul N.

Restricții și precizări

• 1 ≤ N ≤ 1.000.000
• 0 ≤ A, B, C, D ≤ 1.000.000.000
• Pentru 12 puncte, N ≤ 10
• Pentru 8 puncte, pentru orice i < j < k, dacă S[i] = S[k], atunci S[i] = S[j]
• Pentru 11 puncte, B = D = 1.000.000.000, iar A, C ≤ 1000
• Pentru 19 puncte, A = 1, iar fiecare dintre B, C și D poate să fie 1 sau 1.000.000.000
• Pentru 10 puncte, A ≤ 1, iar fiecare dintre B, C și D poate să fie 0, 1 sau 1.000.000.000
• Pentru 11 puncte, N <= 500
• Pentru 8 puncte, N ≤ 100.000
• Pentru 21 puncte, restricții inițiale.

Exemplul 1:

biom.in

6
3 5 4 2
abccbc

biom.out

10

Explicație

Steve se poate mișca cu o poziție la dreapta cu cost 3. De la cubul 2, acesta se poate deplasa spre cubul 5 cu cost 4. La sfârșit, acesta se deplasează din nou cu o poziție la dreapta pentru a ajunge la destinație, cubul 6. Costul total va fi 3 + 4 + 3 = 10.

Exemplul 2:

biom.in

15
1 2 3 4
abccabcbacbabcb

biom.out

11

Explicație

Steve se poate deplasa de la cubul 1 la cubul 5, iar pe urmă la cubul 9, ambele deplasări având fiecare costul 3. Pe urmă, de la cubul 9 se poate deplasa la cubul 10 cu cost 1. De la cubul 10, se poate deplasa la cubul 14 cu cost 3, ca în final să ajungă la destinație, în cubul 15, cu cost 1. Costul total de deplasare va fi 3 + 3 + 1 + 3 + 1 = 11.