UVa 1625

链接：

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])。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int INF = 0x3f3f3f3f;
 7 const int UP = 5000 + 5;
 8 int sa[26], sb[26], ea[26], eb[26]; // sa[i]代表序列a中颜色i的开始位置
 9 int d[2][UP], c[2][UP]; // d[i][j]为两个序列分别移走了i和j个元素的最小费用，c数组记录有多少个颜色已经出现但尚未结束，d, c均为滚动数组
10 char a[UP], b[UP]; // 元素序号从1开始
11 
12 int main(){
13     int T;
14     scanf("%d", &T);
15     while(T--){
16         scanf("%s%s", a+1, b+1);
17         int La = strlen(a+1), Lb = strlen(b+1);
18         for(int i = 0; i < 26; i++) sa[i] = sb[i] = INF, ea[i] = eb[i] = 0;
19         for(int i = 1; i <= La; i++){
20             a[i] -= 'A';
21             sa[a[i]] = min(sa[a[i]], i);
22             ea[a[i]] = i;
23         }
24         for(int i = 1; i <= Lb; i++){
25             b[i] -= 'A';
26             sb[b[i]] = min(sb[b[i]], i);
27             eb[b[i]] = i;
28         }
29 
30         d[0][0] = c[0][0] = 0;
31         for(int j = 0, t = 0; t <= La; t++, j ^= 1){
32             for(int i = 0; i <= Lb; i++){
33                 if(!t && !i) continue;
34 
35                 int v = INF, v2 = INF;
36                 if(t) v = d[j^1][i] + c[j^1][i]; //在a[1..t-1]与b[1..i]后加a[t]
37                 if(i) v2 = d[j][i-1] + c[j][i-1]; //在a[1..t]与b[1..i-1]后加b[i]
38                 d[j][i] = min(v, v2);
39 
40                 if(t){
41                     c[j][i] = c[j^1][i];
42                     if(sa[a[t]] == t && sb[a[t]] > i) c[j][i]++;
43                     if(ea[a[t]] == t && eb[a[t]] <= i) c[j][i]--;
44                 }
45                 else{
46                     c[j][i] = c[j][i-1];
47                     if(sb[b[i]] == i && sa[b[i]] > t) c[j][i]++;
48                     if(eb[b[i]] == i && ea[b[i]] <= t) c[j][i]--;
49                 }
50             }
51         }
52         printf("%d
", d[La&1][Lb]);
53     }
54     return 0;
55 }