luogu#P10566. 「Daily OI Round 4」Analysis

「Daily OI Round 4」Analysis

题目描述

小 C 的信息技术老师给小 C 布置了一项作业,作业内容如下:

有一个字符串,包含大小写字母和数字。你可以把任意一个字符变成另外一个字符,设变化之前字符的 ASCII 码为 aa,变化之后字符的 ASCII 码为 bb,则这次变化消耗 ab|a-b| 的时间。你需要把整个字符串变成只包含大写字母的字符串。

小 C 还有语文数学英语等很多其他重要作业要做,为了节省时间,你需要计算小 C 最少需要多久才能令字符串只包含大写字母。

输入格式

一行一个字符串 ss 表示老师给的字符串。

输出格式

一行一个非负整数 tt,表示令字符串只包含大写字母最少花费多少时间。

AA0aa
31
3kyOu
89

提示

【样例解释】

对于第一组样例,最好的办法是变成 AAAZZ\texttt{AAAZZ},这样的话消耗就为 0+0+4865+9790+9790=310+0+|48-65|+|97-90|+|97-90|=31,容易证明不存在更优的解法。

其中 4848 是字符 0\texttt{0} 的 ASCII 码,6565 是字符 A\texttt{A} 的 ASCII 码,9090 是字符 Z\texttt{Z} 的 ASCII 码,9797 是字符 a\texttt{a} 的 ASCII 码。

【数据范围】

本题开启捆绑测试。

lenlen 为字符串 ss 的长度。

Subtask\text{Subtask} 分值 lenlen \le
00 1010 33
11 3030 1010
22 6060 10510^5

对于全部数据,保证:1len1051 \le len \le 10^5,且 ss 中只包含大小写字母和数字。