https://vjudge.net/problem/UVA-1625
题意：
输入两个长度分别为n和m的颜色序列，要求按顺序合并成同一个序列，即每次可以把一个序列开头的颜色放到新序列的尾部。对于每个颜色c来说，其跨度L（c）等于最大位置和最小位置之差。
思路：
我们用d(i,j)表示两个序列已经分别移走了i和j个元素时的最小代价。当然为了在状态转移时知道每个字母的状态，我们需要一些预处理。在下面的代码中，sp，ep数组分别用来表示序列1中每个字母的开头位置和结束位置，同样的，sq，eq分别用来表示序列1中每个字母的开头位置和结束位置。每次新增一个字符后，所有已经出现的但没有结束的字符的跨度L（c）都要+1。所以，我们还需要设置一个c数组来记录已经开始但还没有结束的字符数。
这样，转移方程就是dp(i,j)=min(dp(i-1,j)+c[i-1][j],dp(i,j-1)+c[i][j-1])。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std; const int maxn = + ;
const int INF = ; char p[maxn], q[maxn];
int sp[], sq[], ep[], eq[];
int d[maxn][maxn], c[maxn][maxn]; int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int T, n, m;
scanf("%d", &T);
while (T--)
{
scanf("%s%s", p + , q + );
//cout << p + 1 << " " << q + 1 << endl;
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] = ;
} //预处理，计算出序列1中每个字符的开始位置和结束位置
for (int i = ; i <= n; i++)
{
sp[p[i]] = min(sp[p[i]], i);
ep[p[i]] = i;
} //预处理序列2
for (int i = ; i <= m; i++)
{
sq[q[i]] = min(sq[q[i]], i);
eq[q[i]] = i;
} for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
if (!i && !j) continue;
int v1 = INF, v2 = INF;
if (i) v1 = d[i-][j] + c[i-][j]; //从p中取颜色
if (j) v2 = d[i][j - ] + c[i][j - ]; //从q中取颜色
d[i][j] = min(v1, v2); //更新c数组
if (i)
{
c[i][j] = c[i - ][j];
if (sp[p[i]] == i && sq[p[i]] > j) c[i][j]++;
if (ep[p[i]] == i && eq[p[i]] <= j) c[i][j]--;
} else if (j)
{
c[i][j] = c[i][j - ];
if (sq[q[j]] == j && sp[q[j]] > i) c[i][j]++;
if (eq[q[j]] == j && ep[q[j]] <= i) c[i][j]--;
}
}
}
cout << d[n][m] << endl;
}
return ;
}
接下来再附上一个滚动数组的代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = + ;
const int INF = ; char p[maxn], q[maxn];
int sp[], sq[], ep[], eq[];
int d[][maxn], c[][maxn]; int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%s%s", p+, q+); int n = strlen(p+);
int m = strlen(q+);
for(int i = ; i <= n; i++) p[i] -= 'A';
for(int i = ; i <= m; i++) q[i] -= 'A'; // calculate s and e
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;
} // dp
int t = ;
memset(c, , sizeof(c));
memset(d, , sizeof(d));
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
if(!i && !j) continue; // calculate d
int v1 = INF, v2 = INF;
//计算d[i][j], d[i][j]由d[i-1][j]或d[i][j-1]添加一个字母得到
if(i) v1 = d[t^][j] + c[t^][j]; // remove from p
if(j) v2 = d[t][j - ] + c[t][j - ]; // remove from q
d[t][j] = min(v1, v2); // calculate 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 ;
}