#P2453. [SDOI2006] 最短距离
[SDOI2006] 最短距离
题目描述
一种 EDIT 字母编辑器,它的功能是可以通过不同的变换操作可以把一个源串 变换为新的目标串 。EDIT 提供的变换操作有:
- 删除源串首个字符(delete);
- 替换源串首个字符放到目标串末尾(replace)。replace 操作可以替换为与原来相同的字符;
- 移动源串首个字符放到目标串末尾(copy);
- 向目标串插入单个字符(insert);
- 交换源串中的两个相邻字符,并移动到目标串末尾中去(twiddle);
- 在完成其它所有操作之后,源串中余下的全部后缀就可用删至行末的操作删除(kill)。
例如,将源 algorithm
转换成目标串 altruistic
的一种方法是采取下面的操作序列:
操作 | 目标串 | 原串 |
---|---|---|
初始 | (空) | algorithm |
copy a |
a |
lgorithm |
copy l |
al |
gorithm |
replace g to t |
alt |
orithm |
delete o |
rithm |
|
copy r |
altr |
ithm |
insert u |
altru |
|
insert i |
altrui |
|
insert s |
altruis |
|
twiddle it into ti |
altruisti |
hm |
replace h to c |
altruistic |
m |
kill |
(空) |
要达到这个结果还可能有其它一些操作序列。
操作 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;
一个给定的操作序列的代价为序列中各操作代价之和。 例如上述操作序列的代价为
$$\begin{aligned}&3\times \mathrm{cost}(\mathtt{copy})+2\times \mathrm{cost}(\mathtt{replace})+\mathrm{cost}(\mathtt{delete})+3\times \mathrm{cost}(\mathtt{insert}) \\ &+\mathrm{cost}(\mathtt{twiddle}) +\mathrm{cost}(\mathtt{kill}) \\ =\ & 3\times 5+2\times 6+3+3\times 4+4+1\times 3-1\\ =\ &48\end{aligned}$$编程任务
给定两个序列 和一些操作代价集合, 到 的最短距离为将 转化为 的最小的转换序列的代价。请给出一个算法来找出 至 的最短距离。
输入格式
第一行:源序列 。
第二行:目标序列 。
第三行: 个正整数,分别是:delete、replace、copy、insert、twiddle 的代价。
输出格式
一行一个整数,表示 到 的最短距离(最小代价和)。
algorithm
altruistic
3 6 5 4 4
48
提示
数据范围及约定
对于全部数据,满足 ,且所有代价均为不大于 的非负整数。