NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem26--最短距离

26: 最短距离

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

一种EDIT字母编辑器,它的功能是可以通过不同的变换操作可以把一个源串X [l..m]变换为新的目标串y[1..n]。EDIT提供的变换操作有:

源串中的单个字符可被删除(delete);

被替换 (replace);

被复制到目标串中去(copy);

字符也可被插入(insert);

源串中的两个相邻字符可进行交换并复制到目标串中去(twiddle);

在完成其它所有操作之后,源串中余下的全部后缀就可用删至行末的操作删除(kill)。

例如,将源"algorithm"转换成目标串"altruistic"的一种方法是采取下面的操作序列:

要达到这个结果还可能有其它一些操作序列。

操作delete,replace,copy,insert,twiddle和kill中每一个都有一个相联系的代价cost。例如

cost(delete)=3;

cost(replace)=6;

cost(copy)=5;

cost(insert)=4;

cost(twiddle)=4;

cost(kill)=被删除的串长*cost(delete)-1;


一个给定的操作序列的代价为序列中各操作代价之和。 例如上述操作序列的代价为

3*cost(copy)+2*cost(replace)+cost(delete)+3*cost(insert) + cost(twiddle) +cost(kill)=3*5+2*6+3+3*4+4+1*3-1=48

编程任务:

给定两个序列x[1..m],y[1..n]和一些操作代价集合,X到Y的最短距离为将X转化为Y的最小的转换序列的代价。请给出一个算法来找出x[1..m]至y[1..n]的最短距离。

Input

第一行:源序列x[1..m]。(m<200)

第二行:目标序列y[1..n]。(n<200)

第三行:5个正整数(<100):分别是:delete 、replace 、copy、 insert、 twiddle的代价。


Output

X到Y的最短距离(最小代价和)。


Sample Input Copy

algorithm
altruistic
3 6 5 4 4

Sample Output Copy

48

Source/Category

其他