题目链接：点击打开链接

有一个交换操作比較特殊，所以记录每一个点距离自己近期的那个字符的位置

然后交换就相当于把第一行要交换的2个字符 之间的字符都删掉

把第二行要交换的2个字符 之间的字符都插入第一行的2个字符之间

然后再进行交换。

#include <cstdio>

#include <cstring>

#include<iostream>

using namespace std;

#define inf 10000000

#define N 4005

#define get_min(a,b) {a=min(a,b);}

int dp[N][N], t1, t2, t3, t4;

int p1[N][30], p2[N][30];

char s[N], t[N];

int n, m;

void input(){

	scanf("%s",s+1);	scanf("%s",t+1);

	n = strlen(s+1);	m = strlen(t+1);

	memset(p1[0], -1, sizeof p1[0]);

	memset(p2[0], -1, sizeof p2[0]);

}

int main(){

	int i,j,x,y;

	while(~scanf("%d %d %d %d",&t1,&t2,&t3,&t4)){

		input();

		for(i = 0; i <= n; i++)for(j = 0; j <= m; j++)dp[i][j] = inf;

		dp[0][0] = 0;

		for(i = n; i ; i--)

		{

			memcpy(p1[i], p1[i+1], sizeof p1[i]);

			p1[i][s[i]-'a']=i;

		}

		for(i = m; i; i--)

		{

			memcpy(p2[i], p2[i+1], sizeof p2[i]);

			p2[i][t[i]-'a']=i;

		}

		for(i = 0; i <= n; i++)

			for(j = 0; j <= m; j++)

			{

				if(s[i+1] == t[j+1])

					get_min(dp[i+1][j+1], dp[i][j]);

				get_min(dp[i+1][j], dp[i][j]+t2);

				get_min(dp[i][j+1], dp[i][j]+t1);

				get_min(dp[i+1][j+1], dp[i][j]+t3);

				if ((x = p1[i + 2][t[j + 1] - 'a']) && (y = p2[j + 2][s[i + 1] - 'a'])) {

				get_min(dp[x][y], dp[i][j] + (x - i - 2) * t2 + (y - j - 2) * t1 + t4);

			}

			}

		cout<<dp[n][m]<<endl;

	}

	return 0;

}