Pracsiu Dan (dnprx) Se dă un șir de n litere mici, în care litera a are asociată valoarea 1, litera b valoarea 2, …, litera z valoarea 26. Se pot efectua oricâte operații de genul: modifică o literă c1 în litera c2 cu un cost c1+c2.
Cerința
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 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
3 ≤ lungimea șirului ≤ 50.000
Exemplu:
nondecreasing.in
dbca
nondecreasing.out
9
Explicație
Modifică d în a cu un cost d+a=4+1=5, apoi modifică ultimul a în c cu un cost a+c=1+3=4. Se obține șirul crescător abcc cu un cost total egal cu 5+4=9.