题目链接：https://www.luogu.com.cn/problem/UVA1625
解题思路：
(s1[1..n],s2[1..m]) 分别表示两个字符串；
(st1[c]) 表示字符 (c) 在字符串 (s1) 中第一次出现的位置；
(ed1[c]) 表示字符 (c) 在字符串 (s1) 中最后一次出现的位置；
(st2[c]) 表示字符 (c) 在字符串 (s2) 中第一次出现的位置；
(ed2[c]) 表示字符 (c) 在字符串 (s2) 中最后一次出现的位置；
(num[i][j]) 表示在 (s1[1..i-1]) 和 (s2[1..j-1]) 中出现过并且在 (s1[i+1..n]) 和 (s2[j+1..m]) 中仍然存在的不同字符有多少个。
(f[i][j]) 表示当前放置好了 (s1[1..i]) 和 (s2[1..j]) 的代价加上给未来带来的额外代价之和。
状态转移方程为：
[f[i][j] = min{ f[i-1][j], f[i][j-1] } + num[i][j]
]
最终的答案即为 (f[n][m])。
由于空间限制，开滚动数组比较好。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050;
char s1[maxn], s2[maxn];
int T, n, m, st1[26], ed1[26], st2[26], ed2[26], f[2][maxn], num[2][maxn];
void init() {
memset(st1, 0, sizeof(st1));
memset(ed1, 0, sizeof(ed1));
memset(st2, 0, sizeof(st2));
memset(ed2, 0, sizeof(ed2));
memset(f, 0, sizeof(f));
memset(num, 0, sizeof(num));
}
int main() {
scanf("%d", &T);
while (T --) {
init();
scanf("%s%s", s1+1, s2+1);
n = strlen(s1+1);
m = strlen(s2+1);
for (int i = 1; i <= n; i ++) {
int c = s1[i] - 'A';
if (!st1[c]) st1[c] = i;
ed1[c] = i;
}
for (int i = 1; i <= m; i ++) {
int c = s2[i] - 'A';
if (!st2[c]) st2[c] = i;
ed2[c] = i;
}
for (int i = 0; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
int s = i & 1;
if (!i && !j) continue; // num[0][0] 已经计算过了
int num1 = -1, num2 = -1;
if (i) { // (i-1, j) --> (i, j)
int c = s1[i] - 'A';
num1 = num[s][j] = num[s^1][j];
if (i == st1[c] && (!st2[c] || j < st2[c])) {
num1 ++;
num[s][j] ++;
}
if (i == ed1[c] && (!ed2[c] || j >= ed2[c])) {
num1 --;
num[s][j] --;
}
}
if (j) { // (i, j-1) --> (i, j)
int c = s2[j] - 'A';
num2 = num[s][j] = num[s][j-1];
if (j == st2[c] && (!st1[c] || i < st1[c])) {
num2 ++;
num[s][j] ++;
}
if (j == ed2[c] && (!ed1[c] || i >= ed1[c])) {
num2 --;
num[s][j] --;
}
}
if (num1 != -1 && num2 != -1) {
assert(num1 == num2);
}
f[s][j] = INT_MAX;
if (i) { // (i-1, j) --> (i, j)
f[s][j] = min(f[s][j], f[s^1][j] + num[s][j]);
}
if (j) { // (i, j-1) --> (i, j)
f[s][j] = min(f[s][j], f[s][j-1] + num[s][j]);
}
}
}
printf("%d
", f[n%2][m]);
}
return 0;
}