PID418 / 浪浪的小爱好
题目描述

浪浪有个小爱好,那就是和MM聊天……其实他还有另一个小爱好,就是学老师说话(我们一些老师的语调特别有特点)。他经常学某老师的一段话,原句由n个音节构成(3<=n<=200000),每个音节用一个小写英文字母表示,相同的字母表示发音相同的音节。虽然浪浪的模仿也由n个音节构成,然而他学得实在不像。

先给出一些定义:每个音节通过一次变换可以变成字母相邻的音节(就是说,a通过一次变换可以变为b,d通过一次变换可以变为c或e,依此类推)。两个音节之间的距离定义为一个音节变换为另一个音节的最少次数(如果两个音节发音相同,那么它们之间的距离为0)。两段音节数相同的语句之间的距离定义为对应音节距离之和。而两段语句之间的差异定义为距离的平方。浪浪模仿得不像,正是在于他的模仿与老师的原句差异太大。

其实浪浪也知道弥补的方法:那就是把整段话拆成若干短来模仿。那么总的差异程度就是每一小段与原句对应段的差异。当然,由于老师的话只有一段,所以浪浪的模仿每增加一段,总的差异度就会加上一个常数m(0<=m<=100000)。然而浪浪却不知道他的模仿与老师原句总差异最小能达到多少。你能帮助他么?

(以上描述可能比较复杂,这里解释样例帮助理解:【样例1】最好的方法是前2个音节为一段,第3个音节为另一段。这样总差异为sqr(1+1)+sqr(2)+2=10;【样例2】最好的方法是第1个音节为第1段,第2~3个音节为第2段,第4~5个音节为第三段。这样总差异为sqr(2)+sqr(1+1)+sqr(2+1)+4+4=25。)

输入格式

第一行为两个整数n,m。第二行为老师原句的n个音节。第三行为浪浪模仿的n个音节。

输出格式

一个整数,表示最小的总差异(保证不超过longint范围)。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论