P2453 [SDOI2006] Shortest Distance

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` | `alt` | `rithm` | | `copy r` | `altr` | `ithm` | | `insert u` | `altru` | `ithm` | | `insert i` | `altrui` | `ithm` | | `insert s` | `altruis` | `ithm` | | `twiddle it into ti` | `altruisti` | `hm` | | `replace h to c` | `altruistic` | `m` | | `kill` | `altruistic` | (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: ```plain 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]$.

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 a single integer in one line, representing the shortest distance (minimum total cost) from $X$ to $Y$.

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