类似于LCS的动态规划，指标函数的分解。
题目链接：
题目大意：两个颜色序列，将他们合并，合并的时候，每次都从开头拿颜色，对于每一个颜色c来说，都有他的跨度l(c)，就是最后的位置与最前的位置的差值，就怎样的排列是的所有l(c)总和最小。
分析：从两个串中随机拿字符，解答树是特别大的。
d(i,j) p拿前 I 个字符， q拿前 j 个字符 所要的代价。
n,m<=5000,二维数组改成滚动数组。
这个时候，不是等到一个颜色全部移动玩了之后再算跨度。而是，只要多少种颜色已经开始但尚未结束，L(c) + 1;
重点再与求代价C。首先计算全部移动Q，只要是该字符开头，代价就加一，但是如果刚好是最后一个就恢复。然后再推数组P时，就可以直接利用已经计算好的c代价数组，只需要根据他更新由于i的加入使得增加的代价。
#includeusing namespace std;#define maxn 5005#define INF 0x3f3f3f3fchar p[maxn],q[maxn];int sp[26],ep[26],sq[26],eq[26];int d[2][maxn],c[2][maxn];int main(){ int t; scanf("%d",&t); while(t--) { scanf("%s%s",p+1,q+1); int n = strlen(p+1); int m = strlen(q+1); for(int i=1; i<=n; i++) p[i] -='A'; for(int i=1; i<=m; i++) q[i] -='A'; for(int i=0; i<26; i++) { sp[i] = sq[i] = INF; ep[i] = eq[i] = 0; } for(int i=1; i<=n; i++) { sp[p[i]] = min(sp[p[i]],i); ep[p[i]] = i; } for(int i=1; i<=m; i++) { sq[q[i]] = min(sq[q[i]],i); eq[q[i]] = i; } memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); int t = 1; //dp for(int i = 0; i <= n; i++) { for(int j = 0; j <= m; j++) { if(!i && !j) continue; int v1 = INF, v2 = INF; if(i) v1 = d[t^1][j] + c[t^1][j]; // 从P上面移动 if(j) v2 = d[t][j - 1] + c[t][j - 1]; // 从Q上面移动 d[t][j] = min(v1, v2); // 更新代价 if(i) { c[t][j] = c[t^1][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 - 1]; 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 ^= 1; } printf("%d\n", d[t^1][m]); } return 0;}
两个颜色序列，将他们合并，合并的时候，每次都从开头拿颜色，对于每一个颜色c来说，都有他的跨度l(c)，就是最后的位置与最前的位置的差值，就怎样的排列是的所有l(c)总和最小。