思路还算明白，不过要落实到代码上还真敲不出来。
题意：
有两个由大写字母组成的颜色序列，将它们合并成一个序列：每次可以把其中一个序列开头的颜色放到新序列的尾部。
对于每种颜色，其跨度定义为合并后的序列中最后一次和第一次出现的位置之差，求所有合并方案中所有颜色跨度之和的最小值。
分析：
d(i, j)表示两个串分别已经移走了i个和j个字符。那么无论新串的顺序是什么，有多少种颜色已经开始但尚未结束是确定的，记为c(i, j)。再继续移走一个字符，所有颜色跨度之和就增加c(i, j)。c的计算是通过记录每种颜色在每个串的始末位置来确定的。
由于数据量较大，还用滚动数组来优化空间复杂度。
//#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ;
const int INF = ;
char p[maxn], q[maxn];
int sp[], ep[], sq[], eq[]; //记录两个串每种颜色的始末
int d[][maxn], c[][maxn]; //c[i][j]表示d[i][j]时还有多少种颜色已经开始但尚未结束 int main(void)
{
#ifdef LOCAL
freopen("1625in.txt", "r", stdin);
#endif int n, m, T;
scanf("%d", &T);
while(T--)
{
scanf("%s", p+);
scanf("%s", q+);
n = strlen(p+);
m = strlen(q+);
for(int i = ; i <= n; ++i) p[i] -= 'A';
for(int i = ; i <= m; ++i) q[i] -= 'A'; for(int i = ; i < ; ++i) { sp[i] = sq[i] = INF; ep[i] = eq[i] = ; }
for(int i = ; i <= n; ++i)
{
sp[p[i]] = min(sp[p[i]], i);
ep[p[i]] = i;
}
for(int i = ; i <= m; ++i)
{
sq[q[i]] = min(sq[q[i]], i);
eq[q[i]] = i;
} int t = ;
memset(d, , sizeof(d));
memset(c, , sizeof(c));
for(int i = ; i <= n; ++i)
{
for(int j = ; j <= m; ++j)
{
if(!i && !j) continue; int v1, v2;
v1 = v2 = INF;
if(i) v1 = d[t^][j] + c[t^][j];
if(j) v2 = d[t][j-] + c[t][j-];
d[t][j] = min(v1, v2);
//计算c
if(i)
{
c[t][j] = c[t^][j];
if(sp[p[i]] == i && sq[p[i]] > j) c[t][j]++;
if(ep[p[i]] == i && eq[p[i]] <= j) c[t][j]--;
}
else if(j)
{
c[t][j] = c[t][j-];
if(sq[q[j]] == j && sp[q[j]] > i) c[t][j]++;
if(eq[q[j]] == j && ep[q[j]] <= i) c[t][j]--;
}
}
t ^= ;
}
printf("%d\n", d[t^][m]);
} return ;
}
代码君