Description

An EDIT string editor can transform a source string $X[1\cdots m]$ into a new target string $Y[1\cdots n]$ via different operations. EDIT provides the following operations:

• delete: delete the first character of the source string.
• replace: replace the first character of the source string and append it to the end of the target string. The replace operation may replace it with the same character as the original.
• copy: move the first character of the source string to the end of the target string.
• insert: insert a single character into the target string.
• twiddle: swap the first two adjacent characters of the source string, and move them to the end of the target string.
• kill: after finishing all other operations, the remaining suffix of the source string can be deleted by a delete-to-end operation.

For example, one way to transform the source algorithm into the target string altruistic is to perform the following sequence of operations:

Operation	Target string	Source string
Initial	(empty)	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		(empty)

There may be other operation sequences that achieve this result as well.

Each of the operations delete, replace, copy, insert, twiddle, and kill has an associated cost. For example:

cost(delete) =3;
cost(replace)=6;
cost(copy)   =5;
cost(insert) =4;
cost(twiddle)=4;
cost(kill) = 被删除的串长 * cost(delete) - 1;

The cost of a given operation sequence is the sum of the costs of the operations in the sequence. For example, the cost of the above sequence is

$$\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}$$

Programming Task

Given two sequences $X[1\cdots m], Y[1\cdots n]$ and a set of operation costs, the shortest distance from $X$ to $Y$ is the minimum cost of a sequence of operations that transforms $X$ into $Y$. Please give an algorithm to find the shortest distance from $X[1\cdots m]$ to $Y[1\cdots n]$.

Input Format

The first line: the source sequence $X[1\cdots m]$.

The second line: the target sequence $Y[1\cdots n]$.

The third line: $5$ positive integers, which are the costs of delete, replace, copy, insert, and twiddle, in this order.

Output Format

Output a single integer in one line, representing the shortest distance (minimum total cost) from $X$ to $Y$.

algorithm
altruistic
3 6 5 4 4

48

Hint

Constraints

For all testdata, $1 \le n, m \le 200$, and all costs are nonnegative integers no greater than $100$.

Translated by ChatGPT 5