13125: 字符串比较问题
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:1
Solved:0
Description
对于长度相同的2个字符串A和B,其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值;空格与空格的距离为0,空格与其他字符的距离为一个定值k。在一般情况下,字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中,有一对距离最短的扩展,该距离称为字符串A和B的扩展距离。对于给定的字符串A和B,设计一个算法,计算其扩展距离。
提示:设字符串A和B的字串A[1...i]和B[1...j]的扩展距离是val(i, j);
val(i, j)具有最优子结构性质,且满足如下递推式:
val(i, j) = min{ val(i-1, j) + k,val(i, j) + k,val(i-1, j-1) + dist(ai , bi) }。可以参考教材上面的最长公共子序列的解法。
Input
第一行:字符串A
第二行:字符串B
第三行:空格与其他字符的距离定制k.
Output
第一行:字符串A和B的扩展距离。
Sample Input Copy
goodluck
iamfine
5
Sample Output Copy
33