Time limit: 0.04s
Memory limit: 256MB
Input: nondecreasing.in
Output: nondecreasing.out
Se dă un șir de litere mici, în care litera a
are asociată valoarea , litera b
valoarea , , litera z
valoarea . Se pot efectua oricâte operații de genul: modifică o literă în litera cu un cost .
Cerință
Să se determine costul total minim al unor operații astfel încât șirul să devină crescător.
Date de intrare
Fișierul de intrare nondecreasing.in
va conține pe prima linie șirul de litere mici, fără spații.
Date de ieșire
Fișierul de ieșire nondecreasing.out
va conține un singur număr natural ce reprezintă costul total minim al tuturor operațiilor care conduc la formarea unui șir crescător.
Restricții și precizări
- Lungimea șirului este cuprinsă între și .
Exemplu
nondecreasing.in
dbca
nondecreasing.out
9
Explicație
Modifică d
în a
cu un cost , apoi modifică ultimul a
în c
cu un cost . Se obține șirul crescător abcc
cu un cost total egal cu .