记录编号	39055	评测结果	AAAAAAAAAT
题目名称	DNA重组	最终得分	90
用户昵称	CC	是否通过	未通过
代码语言	C++	运行时间	4.191 s
提交时间	2012-07-03 19:02:19	内存使用	69.19 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define INF 1027423549
using namespace std;
int T,n,m,o;
int f[3005][3005][2];
char a[3005],b[3005];
int main() {
	freopen("dna.in","r",stdin);
	freopen("dna.out","w",stdout);
	scanf("%d\n", &T);
	while (T--) {
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		scanf("%s",a + 1);
		scanf("%s",b + 1);
		m = strlen(a + 1);
		n = strlen(b + 1);
		memset(f,61,sizeof(f));
		for (int i = 1;i <= n;i++) 
			for (int j = i;j <= m;j++) {
				if (b[i] == a[j]) {
					if (i == 1) {
						if (j == 1) f[i][j][1] = 0;
						else f[i][j][1] = 1;
					} else f[i][j][1] = min(f[i - 1][j - 1][0] + 2,f[i - 1][j - 1][1]);
				}
				f[i][j][0] = min(f[i][j - 1][1] + 1,f[i][j - 1][0]);
			}
		int ans = min(f[n][m][0],f[n][m][1]);
		if (ans == INF) ans = -1;
		printf("%d\n", ans);
	}
	return 0;
}