[SDOI2006]最短距离题解

[SDOI2006]最短距离题解——HM题目描述一种EDIT字母编辑器它的功能是可以通过不同的变换操作可以把一个源串X [l..m]变换为新的目标串y[1..n]。EDIT提供的变换操作有源串中的单个字符可被删除(delete)被替换 (replace)被复制到目标串中去(copy)字符也可被插入(insert)源串中的两个相邻字符可进行交换并复制到目标串中去(twiddle)在完成其它所有操作之后源串中余下的全部后缀就可用删至行末的操作删除(kill)。例如将源algorithm转换成目标串altruistic的一种方法是采取下面的操作序列:要达到这个结果还可能有其它一些操作序列。操作delete,replacecopyinserttwiddle和kill中每一个都有一个相联系的代价cost。例如cost(delete)3; cost(replace)6; cost(copy)5; cost(insert)4; cost(twiddle)4; cost(kill)被删除的串长*cost(delete)-1;一个给定的操作序列的代价为序列中各操作代价之和。 例如上述操作序列的代价为3*cost(copy)2*cost(replace)cost(delete)3*cost(insert) cost(twiddle) cost(kill)3*52*633*441*3-148编程任务给定两个序列x[1..m],y[1..n]和一些操作代价集合X到Y的最短距离为将X转化为Y的最小的转换序列的代价。请给出一个算法来找出x[1..m]至y[1..n]的最短距离。输入格式第一行源序列x[1..m]。m200第二行目标序列y[1..n]。(n200)第三行5个正整数100分别是delete 、replace 、copy、 insert、 twiddle的代价。输出格式X到Y的最短距离最小代价和。输入输出样例输入 #1algorithm altruistic 3 6 5 4 4输出 #148题解一道挺考验码力的题。看完题目应该会发现这是一道dp题但dp方程比较复杂因为状态比较多。设我们有dp[i][j]表示初始串操作到第i位目标串完成到第j位则各个操作的状态转移方程为delete:dp[i][j]min(dp[i][j],dp[i-1][j]cost[1])replace:dp[i][j]min(dp[i][j],dp[i-1][j-1]cost[2])copydp[i][j]min(dp[i][j],dp[i-1][j-1]cost[3])insert:dp[i][j]min(dp[i][j],dp[i][j-1]cost[4])twiddle:dp[i][j]min(dp[i][j],dp[i-2][j-2]cost[5])kill:dp[Len1][Len2]min(dp[Len1][Len2],dp[i][Len2]cost[1]*(Len1-i)-1)解释一下delete操作中将初始串第i位的前一位即删除一个字符时加上删除代价便是状态将其与当前状态比较即可。前5个操作都是如此可以理解一下应该比较简单吧。最后一个操作也很好理解因为kill操作优于delete操作(最后-1)当目标串已经完成时进行枚举按照题目要求进行操作即可。大约就这样了注意每个情况的条件与特殊情况即可。附代码#include bits/stdc.h using namespace std; const int SIZE205; const int INF0x3f3f3f3f; #define ll long long char s1[SIZE],s2[SIZE]; int dp[SIZE][SIZE],cost[10]; int Len1,Len2; int main() { // cins1s2; scanf(%s%s,s11,s21); for (int i1;i5;i) scanf(%d,cost[i]); Len1strlen(s11); Len2strlen(s21); memset(dp,INF,sizeof(dp)); if (Len1!0 Len20){ printf(%d,Len1*cost[1]); return 0; } if (Len10 Len2!0){ printf(%d,Len2*cost[4]); return 0; } dp[0][0]0; for (int i1;iLen1;i) dp[i][0]i*cost[1]; for (int i1;iLen2;i) dp[0][i]i*cost[4]; for (int i1;iLen1;i) for (int j1;jLen2;j){ if (s1[i]s2[j]) dp[i][j]min(dp[i][j],dp[i-1][j-1]cost[3]); dp[i][j]min(dp[i][j],min(dp[i-1][j-1]cost[2],min(dp[i-1][j]cost[1],dp[i][j-1]cost[4]))); if (i1 || j1) continue; if (s1[i-1]s2[j] s1[i]s2[j-1]) dp[i][j]min(dp[i][j],dp[i-2][j-2]cost[5]); } for (int i1;iLen1;i) dp[Len1][Len2]min(dp[Len1][Len2],(Len1-i)*cost[1]dp[i][Len2]-1); printf(%d,dp[Len1][Len2]); return 0; }吐槽貌似这题与状态压缩没有太大关系。谢谢观看