U527240 # 编辑距离

给一个字符串，为字符设置一个排序，即为每个字符分配一个位置编号 $pos$，使得所有字符串中相邻两个字符的距离之和最小？

您有一个经常输入的密码，一个长度为 $n$ 的字符串 $s$ 。该字符串的每个字符都是前 $m$ 个小写字符之一。 由于您花了大量时间输入密码，因此您想买一个新键盘。键盘是前 $m$ 个小写字母的排列组合。 由于您只用一根手指输入密码，因此您需要花费时间将手指从一个密码字符移动到下一个字符。从字符 $s_i$ 移动到字符 $s_{i+1}$ 的时间等于这些字符在键盘上的距离。使用键盘输入密码所需的总时间称为该键盘的编辑距离。 假设字符 $c$ 在键盘上的位置为 $pos_c$ ,则键盘的编辑距离为 $\sum_{i=1}^{n-1} |pos_{s_i}-pos_{s_{i+1}}|$ 。 你需要购买对于你的密码来说编辑距离最小的一款键盘。

无

无

对于 $30 \%$ 的数据：$1\le n\le 100,1\le m\le 9$ 对于 $60 \%$ 的数据：$1\le n\le 10^5,1\le m\le 9$ 对于 $100 \%$ 的数据：$1\le n\le 10^5,1\le m\le 20$