D10T1
前三种转移和编辑距离（没有操作四，且权值为1）一样，所以重点看第四个怎么转移。
第四种有两种，一种是疯狂交换相邻的两个，直到把两个数交换，另一种则是先把他们之间的值都删除，再交换，然后再插入。
因为题目中说 2d \ge a+b 所以是第二种更有。
那么就预处理，当前交换那个可以匹配上，即和当前位置交换的位置是哪里，然后可以 O(n) 预处理，然后 O(nm) 转移。
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 4e3 + 5;
void cmin(int &x, int y) {x = x < y ? x : y;}
char a[N], b[N];
int n, m, ti, td, tr, te, na[N][26], nb[N][26], f[N][N];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> ti >> td >> tr >> te >> (a + 1) >> (b + 1);
n = strlen(a + 1), m = strlen(b + 1), cmin(tr, ti + td);
memset(na, 0x3f, sizeof(na)), memset(nb, 0x3f, sizeof(nb));
for(int i = n; i; i--) memcpy(na[i], na[i + 1], 104), na[i][a[i] - 'a'] = i;
for(int i = m; i; i--) memcpy(nb[i], nb[i + 1], 104), nb[i][b[i] - 'a'] = i;
memset(f, 0x3f, sizeof(f)), f[0][0] = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= m; j++) {
if(a[i + 1] == b[j + 1]) cmin(f[i + 1][j + 1], f[i][j]);
cmin(f[i][j + 1], f[i][j] + ti);
cmin(f[i + 1][j], f[i][j] + td);
cmin(f[i + 1][j + 1], f[i][j] + tr);
if(i + 2 <= n && j + 2 <= m) {
int p = nb[j + 2][a[i + 1] - 'a'];
int q = na[i + 2][b[j + 1] - 'a'];
if(p < N && q < N) cmin(f[q][p], f[i][j] + te + (p - (j + 2)) * ti + (q - (i + 2)) * td);
}
}
printf("%d\n", f[n][m]);
return 0;
}