 /**//*
问将串A变到串B的最小时间,不过多了一种方法就是交换相邻
插入、删除、替换、交换的时间为ti,td,tr,te
不过题目给出了2te>=ti+td

一开始不会做,看了解题报告提到Damerau Levenshtein distance
http://www.itbhu.ac.in/codefest/problem.php?pid=101
Wiki上有Damerau Levenshtein distance
看了bobchennan的代码

由于2te>=ti+td,所以A的第i个字母不会跟前面的交换2次,最多只有1次!!!!!!
有了这个之后,就用la[26],lb[26]记录在状态(i,j)之前,A,B串中各种字母的位置
“交换”的这种转移就是多寻找一个ii,jj,其中A[ii] == B[j] && A[i] == B[jj]
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;

const int MAXN = 5000;
const int INF = 0x3f3f3f3f;

char A[MAXN], B[MAXN];
int dp[MAXN][MAXN];
int la[26],lb[26];

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif

 for(int ti, td, tr, te; cin>>ti>>td>>tr>>te; ) {
scanf("%s%s", A+1, B+1);
int lenA = strlen(A+1), lenB = strlen(B+1);
dp[0][0] = 0;
 for (int i = 1; i <= lenA ; i++) {
dp[i][0] = td*i;
}
 for ( int j = 1 ; j <= lenB ; j++) {
dp[0][j] = ti*j;
}
fill(la,la+26,0);
 for (int i = 1; i <= lenA ; i++) {
fill(lb,lb+26,0);
 for(int j = 1; j <= lenB ; j ++) {
dp[i][j] = INF;
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + tr*(A[i] != B[j]));
dp[i][j] = min(dp[i][j], dp[i-1][j] + td);
dp[i][j] = min(dp[i][j], dp[i][j-1] + ti);
int ii = la[B[j]-'a'], jj = lb[A[i]-'a'];
 if(ii > 0 && jj > 0) {
dp[i][j] = min(dp[i][j], dp[ii-1][jj-1] + te + (i-ii-1)*td + (j-jj-1)*ti);//swap(ii,i)
}
lb[B[j]-'a'] = j;
}
la[A[i]-'a'] = i;
}
printf("%d\n", dp[lenA][lenB]);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|