学步园

看到后面例题9-21也用了这题的方法，把这题补上

这题：在放置颜色的时候，需要判断它是不是最后一个，然后需要找到这个颜色的开始位置。如果把每个颜色的开始位置记录在状态中，状态空间将会太大

但是每次放置颜色，如果有 a 种颜色还没有结束，那么这 a 种颜色结束的时候，与初始位置的距离肯定要+1。每种颜色开始和结束的位置我们可以事先算出，因此我们可以在状态转移的时候判断当前还有多少种颜色没有结束。

根据这个性质，我们可以在状态中只记录两个序列的当前位置。状态转移时，累加没有结束的颜色的种类数量。

我一开始预处理每个 i 和 j 对应的颜色种类数量，三层循环（i j 和颜色）速度太慢，TLE了。后来参考了代码仓库，改为了：每次转移，在(i-1,j)或(i,j-1)的基础上判断是否有颜色开始/结束来确定(i,j)的颜色种类数量。

另外，dp(i,j) 最好设计成“已经放置了第一列的前 i 个，第二排的前 j 个，剩下的代价是多少”，而不是“放置第一排的 i-n 和第二排的 j-n，代价是多少 ”。后者在判断颜色的开始和结束时比较不方便。

Run Time: 0.012s

#define UVa  "LT9-8.1625.cpp"		//
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

//Global Variables. Reset upon Each Case!
const int INF = 99999999, maxn = 5000 + 5, maxc = 30;
int T, n, m;
char s1[maxn], s2[maxn];
int start[maxc][2], end[maxc][2];
int d[maxn][maxn];
int c[maxn][maxn];
/////

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%s%s", s1+1, s2+1);
        n = strlen(s1+1);
        m = strlen(s2+1);
        memset(start, -1, sizeof(start));
        memset(end, -1, sizeof(end));

        for(int i = 0; i < 30; i ++)
            start[i][0] = start[i][1] = maxn;

        for(int i = 1; i <= n; i ++) {
            int c = s1[i] - 'A';
            if(start[c][0] == maxn) start[c][0] = i;
            end[c][0] = i;
        }
        for(int i = 1; i <= m; i ++) {
            int c = s2[i] - 'A';
            if(start[c][1] == maxn) start[c][1] = i;
            end[c][1] = i;
        }
        d[0][0] = 0;
        c[0][0] = 0;
        for(int i = 0; i <= n; i ++) {
            for(int j = 0; j <= m; j ++) {
                if(i && j) d[i][j] = min(d[i-1][j] + c[i-1][j], d[i][j-1] + c[i][j-1]);
                else if(i) d[i][j] = d[i-1][j] + c[i-1][j];
                else d[i][j] = d[i][j-1] + c[i][j-1];
                if(i) {
                    c[i][j] = c[i-1][j];
                    int color = s1[i]-'A';
                    if(i == start[color][0] && j < start[color][1]) c[i][j] ++;
                    if(i == end[color][0] && j >= end[color][1]) c[i][j] --;
                }
                else if(j){
                    c[i][j] = c[i][j-1];
                    int color = s2[j]-'A';
                    if(j == start[color][1] && i < start[color][0]) c[i][j] ++;
                    if(j == end[color][1] && i >= end[color][0]) c[i][j] --;
                }
            }
        }
        printf("%d\n", d[n][m]);
    }

    return 0;
}