http://acm.hust.edu.cn/vjudge/contest/view.action?cid=105116#problem/C
紫书P276
res[i][j]表示第一个序列移动i个，第二个序列移动j个之后有几个已经出现但尚未结束,dp[i][j]表示第一个序列移动i个，第二个序列移动j个之后的总长度
dp[i][j] = min(dp[i - 1][j],dp[i][j - 1]) + res[i][j]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = + ;
const int INF = 0x3f3f3f3f;
char str1[MAX],str2[MAX];
int dp[MAX][MAX],res[MAX][MAX];
int start1[],End1[],start2[],End2[],vis[];
int n,m;
int main()
{
int tase;
scanf("%d", &tase);
while(tase--)
{
scanf("%s%s", str1 + ,str2 + );
n = strlen(str1 + );
m = strlen(str2 + );
memset(vis, , sizeof(vis));
memset(End1, -, sizeof(End1));
memset(End2, -, sizeof(End2));
for(int i = ; i < ; i++)
start1[i] = start2[i] = INF;
for(int i = ; i <= n; i++)
{
if(start1[str1[i] - 'A'] == INF)
start1[str1[i] - 'A'] = i;
End1[str1[i] - 'A'] = i;
}
for(int i = ; i <= m; i++)
{
if(start2[str2[i] - 'A'] == INF)
start2[str2[i] - 'A'] = i ;
End2[str2[i] - 'A'] = i;
} memset(res, , sizeof(res));
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
int cnt = ;
for(int k = ; k < ; k++)
{
if(start1[k] == INF && start2[k] == INF)
continue;
if(start1[k] > i && start2[k] > j)
continue;
if(End1[k] <= i && End2[k] <= j)
continue;
cnt++;
}
res[i][j] = cnt;
}
} dp[][] = ;
for(int i = ; i <= m ; i++)
dp[][i] = dp[][i - ] + res[][i];
for(int j = ; j <= n; j++)
dp[j][] = dp[j - ][] + res[j][];
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
dp[i][j] = min(dp[i - ][j], dp[i][j - ]) + res[i][j];
}
} printf("%d\n", dp[n][m]); } return ;
}
TLE