D10T1
DP。$f_{i,j}$表示字符串A的前i位与字符串B的前j位可以匹配。考虑转移。
opt1:f_{i, j} = f{i, j - 1} + a
opt2:f_{i, j} = f_{i - 1, j} + b
opt3:$f_{i, j} = f_{i - 1, j - 1} + c$特别的$f_{i, j} = f_{i - 1, j - 1} (a_i == b_j)$
考虑转换操作，我们根据${2d} \ge {a + b}$发现一个特性。一段连续的字符子串只会转换1次。假设q是字符$b_j$在A中—— p是$a_i$在B中上一次出现的位置，也就是说明在删去$\left[q, a_i\right]$,然后交换$q, a_i$,添加$\left[p, b_i\right]$及可得到答案
opt4:f_{i,j} = f_{q,p} + (i - q - 1) * b + (j - p - 1) * a
需要注意的是状态的初值只需要设置成为f[0][0] = 0就行了
最终转移的目标是f[n][m]
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cstring>
#define lfor(i, x, y) for (int i = (x); i <= (y); ++ i)
#define llfor(i, x, y) for (int i = (x); i < (y); ++ i)
#define rfor(i, x, y) for (int i = (x); i >= (y); -- i)
#define rlfor(i, x, y) for (int i = (x); i > (y); -- i)
#define For(i, p) for(int i = head[p]; i; i = nxt[i])
template <typename T>inline void read(T &x){bool f=0;x=0;char ch=getchar();while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();if(ch=='-')ch=getchar(),f=1;while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x=f?-x:x;}
template <typename T1,typename... T2>inline void read(T1 &x,T2& ...y){read(x);read(y...);}
using namespace std;
const int N = 4005;
const int M = 30;
char x[N], y[N];
int f[N][N];
int pos1[N][M], pos2[N][M];
int main() {
int a, b, c, d; read(a, b, c, d);
cin >> (x + 1) >> (y + 1);
int n = strlen(x + 1), m = strlen(y + 1);
memset(pos1, 0x3f, sizeof(pos1)), memset(pos2, 0x3f, sizeof(pos2));
rfor(i, n, 0) memcpy(pos1[i], pos1[i + 1], 104), pos1[i][x[i] - 'a'] = i;
rfor(i, m, 0) memcpy(pos2[i], pos2[i + 1], 104), pos2[i][y[i] - 'a'] = i;
memset(f, 0x3f, sizeof(f)); f[0][0] = 0;//TODO
lfor(i, 0, n) {
lfor(j, 0, m) {
if (x[i + 1] == y[j + 1]) f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
f[i][j + 1] = min(f[i][j] + a, f[i][j + 1]);
f[i + 1][j] = min(f[i][j] + b, f[i + 1][j]);
f[i + 1][j + 1] = min(f[i][j] + c, f[i + 1][j + 1]);
if (i + 2 <= n && j + 2 <= m){
int p = pos2[j + 2][x[i + 1] - 'a'], q = pos1[i + 2][y[j + 1] - 'a'];
//cout << "i:" << i << " j:" << j << endl;
//cout << x[i + 1] << " " << y[j + 1] << endl;
//cout << "p:" << p << " q:" << q << endl;
//cout << f[i][j] + (p - (j + 2)) * b + (q - (i + 2)) * a + d << endl;
if (p < N && q < N) f[q][p] = min(f[q][p], f[i][j] + (p - (j + 2)) * a + (q - (i + 2)) * b + d);
}
//cout << "i:" << i << " j:" << j << " f:" << f[i][j] << endl;
//cout << f[i][j] + a << " " << f[i][j] + b << " " << f[i][j] + c << " " << endl;
}
}
cout << f[n][m] << endl;
return 0;
}