这题看题解看了很久，学到了挺多（自己还是太弱，唉！）
（1）这道题的思路非常的巧妙。我一开始看到就觉得不好来记录开始位置以及
结束位置。但是题解换了一个思路，记录每一次开始了但还没有结束的字符有多少个
这样每次进来一个新的字符，就可以更新答案。
（2）这一类两个字符串取公共部分的题，有一个大概的套路。
可以设f[i][j]为第一个字符串用了前i个，第二个字符串用了前j个的情况
然后转移的时候用f[i-1][j]和f[i][j-1]进行处理
（3）滚动数组省空间。当数组只涉及到最近几层的时候可以用滚动数组
比如01背包，每次只需要用到上一行的，所以直接用一维就ok，只是枚举要逆序
然而这道题的转移，不仅涉及到当前一层，还涉及到上一层(d[i-1][j]与c[i][j-1])
所以要用两个数组，用t不断取异或变成0和1来维护。
摸板大致是这样
int t = 0; //初始化
memset() //数组清空
REP(i, 0, n)
{REP(j, 0, m){i -> t //当前这一层 i - 1 -> t ^ 1 //上一层 }t ^= 1;
}
printf("%d\n", f[t^1][m-1]); //最后是t ^ 1
//t是当前这一层,但是最后t又异或了一次，所以是t ^ 1
（4）在动规题目中字符串从1开始比较方便，例如0的位置可以用来初始化，表示这个字符串没有的时候
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 5123;
char p[MAXN], q[MAXN];
int sp[26], ep[26], sq[26], eq[26];
int d[2][MAXN], c[2][MAXN]; int main()
{int n, m, T;scanf("%d", &T);while(T--){scanf("%s%s", p + 1, q + 1);int n = strlen(p + 1), m = strlen(q + 1);REP(i, 1, n + 1) p[i] -= 'A';REP(i, 1, m + 1) q[i] -= 'A';REP(i, 0, 26){sp[i] = sq[i] = 1e9;ep[i] = eq[i] = 0;}REP(i, 1, n + 1){sp[p[i]] = min(sp[p[i]], i);ep[p[i]] = i;}REP(i, 1, m + 1){sq[q[i]] = min(sq[q[i]], i);eq[q[i]] = i;}int t = 0;memset(c, 0, sizeof(c));memset(d, 0, sizeof(d));REP(i, 0, n + 1){REP(j, 0, m + 1){if(!i && !j) continue;int v1 = 1e9, v2 = 1e9;if(i) v1 = d[t ^ 1][j] + c[t ^ 1][j];if(j) v2 = d[t][j - 1] + c[t][j - 1];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;
}