P2453 [SDOI2006]最短距離

一種EDIT字母編輯器，它的功能是可以通過不同的變換操作可以把一個源串X [l..m]變換為新的目标串y[1..n]。EDIT提供的變換操作有：

源串中的單個字元可被删除(delete)；

被替換 (replace)；

被複制到目标串中去(copy)；

字元也可被插入(insert)；

源串中的兩個相鄰字元可進行交換并複制到目标串中去(twiddle)；

在完成其它所有操作之後，源串中餘下的全部字尾就可用删至行末的操作删除(kill)。

例如，将源"algorithm"轉換成目标串"altruistic"的一種方法是采取下面的操作序列:

要達到這個結果還可能有其它一些操作序列。

操作delete,replace，copy，insert，twiddle和kill中每一個都有一個相聯系的代價cost。例如

一個給定的操作序列的代價為序列中各操作代價之和。 例如上述操作序列的代價為

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]的最短距離。

輸入格式：

第一行：源序列x[1..m]。（m<200）

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

第三行：5個正整數（<100）：分别是：delete 、replace 、copy、 insert、 twiddle的代價。

輸出格式：

X到Y的最短距離（最小代價和）。

輸入樣例#1： 

輸出樣例#1： 

Solution：

　　本題線性dp。

　　字元串dp套路，定義狀态$f[i][j]$表示目标串比對$i$個原串操作了$j$個的最小代價，并用$w[i]$表示各操作的花費。

　　那麼初始狀态：$f[0][i\in 1\rightarrow n]=w[1]*i$（删除原串前$i$個字元），$f[i\in 1\rightarrow m][0]=w[4]*$（插入目标串前$i$個字元）。

　　那麼轉移（取$min$）：

　　　　1、删除：$f[i][j]=f[i][j-1]+w[1]$。

　　　　2、替換：$f[i][j]=f[i-1][j-1]+w[2]$。

　　　　3、複制：前提$s[i]==t[j]$，則$f[i][j]=f[i-1][j-1]+w[3]$。

　　　　4、插入：$f[i][j]=f[i-1][j]+w[4]$。

　　　　5、複制交換：前提$s[i-1]==t[j]$且$s[i]==t[j-1]$，則$f[i][j]=f[i-2][j-2]+w[5]$。

　　最後的時候還得對目标串比對完了而原串操作到$i$位置進行字尾删除，即$f[m][i]=f[m][i]+(n-i)*w[6]-1$。

代碼：