#P2453. [SDOI2006] 最短距离

    ID: 1461 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选山东2006状态压缩状压动态规划dp

[SDOI2006] 最短距离

题目描述

一种 EDIT 字母编辑器,它的功能是可以通过不同的变换操作可以把一个源串 X[lm]X[l\cdots m] 变换为新的目标串 Y[1n]Y[1\cdots n]。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}$$

编程任务

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

输入格式

第一行:源序列 X[1m]X[1\cdots m]

第二行:目标序列 Y[1n]Y[1\cdots n]

第三行:55 个正整数,分别是:delete、replace、copy、insert、twiddle 的代价。

输出格式

一行一个整数,表示 XXYY 的最短距离(最小代价和)。

algorithm
altruistic
3 6 5 4 4
48

提示

数据范围及约定

对于全部数据,满足 1n,m2001\le n,m\le 200,且所有代价均为不大于 100100 的非负整数。