链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4500
题意：
输入两个长度分别为n和m（n,m≤5000）的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。
对于每个颜色c来说，其跨度L(c)等于最大位置和最小位置之差。你的任务是找一种合并方式，使得所有L(c)的总和最小。
分析：
首先，因为选取顺序的问题，该题满足无后效性。
也满足最优子结构性质：当在部分最终序列的后面添加一个颜色时，需要把所有“已经出现但还没结束”的颜色的L(c)值加1。
这样，部分最终序列的L(c)值之和越小越好，即只需保留其最小值。
设d(i,j)表示两个序列已经分别移走了i和j个元素的最小费用。
当把一个颜色移到最终序列前，需要把所有“已经出现但还没结束”的颜色的L(c)值加1。
因为并不关心每个颜色的L(c)，所以只需要知道有多少种颜色已经开始但尚未结束。
这样，可以事先算出每个颜色在两个序列中的开始和结束位置，
就可以在动态规划时在O(1)时间内计算出状态d(i,j)中“有多少个颜色已经出现但尚未结束”（用c数组记录）。
因为序列a[1..i]与序列b[1...j]组成的序列的最后一个字符必然是a[i]或b[j]，
所以状态转移方程为：dp(i,j) = min(dp(i-1,j) + c[i-1][j] , dp(i,j-1) + c[i][j-1])。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int INF = 0x3f3f3f3f;
const int UP = + ;
int sa[], sb[], ea[], eb[]; // sa[i]代表序列a中颜色i的开始位置
int d[][UP], c[][UP]; // d[i][j]为两个序列分别移走了i和j个元素的最小费用，c数组记录有多少个颜色已经出现但尚未结束，d, c均为滚动数组
char a[UP], b[UP]; // 元素序号从1开始 int main(){
int T;
scanf("%d", &T);
while(T--){
scanf("%s%s", a+, b+);
int La = strlen(a+), Lb = strlen(b+);
for(int i = ; i < ; i++) sa[i] = sb[i] = INF, ea[i] = eb[i] = ;
for(int i = ; i <= La; i++){
a[i] -= 'A';
sa[a[i]] = min(sa[a[i]], i);
ea[a[i]] = i;
}
for(int i = ; i <= Lb; i++){
b[i] -= 'A';
sb[b[i]] = min(sb[b[i]], i);
eb[b[i]] = i;
} d[][] = c[][] = ;
for(int j = , t = ; t <= La; t++, j ^= ){
for(int i = ; i <= Lb; i++){
if(!t && !i) continue; int v = INF, v2 = INF;
if(t) v = d[j^][i] + c[j^][i]; //在a[1..t-1]与b[1..i]后加a[t]
if(i) v2 = d[j][i-] + c[j][i-]; //在a[1..t]与b[1..i-1]后加b[i]
d[j][i] = min(v, v2); if(t){
c[j][i] = c[j^][i];
if(sa[a[t]] == t && sb[a[t]] > i) c[j][i]++;
if(ea[a[t]] == t && eb[a[t]] <= i) c[j][i]--;
}
else{
c[j][i] = c[j][i-];
if(sb[b[i]] == i && sa[b[i]] > t) c[j][i]++;
if(eb[b[i]] == i && ea[b[i]] <= t) c[j][i]--;
}
}
}
printf("%d\n", d[La&][Lb]);
}
return ;
}