记录编号	39045	评测结果	AAAAAAAAAA
题目名称	DNA重组	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	1.690 s
提交时间	2012-07-03 17:31:09	内存使用	62.48 MiB

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
const int N = 3000 + 10, INF = 0x7ffffff;
int n, m, s, t, f[N][N][2];
char a[N], b[N];
int main() {
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);
    scanf("%d\n", &t);
    while(t--) {
        scanf("%s\n", a+1);
        scanf("%s\n", b+1);
        n = strlen(a+1);
        m = strlen(b+1);
        for(int i=1; i<=n; i++)
            f[i][0][0] = 1, f[i][0][1] = 0;
        for(int i=1; i<=m; i++)
            f[0][i][0] = f[0][i][1] = INF;
        f[0][0][0] = f[0][0][1] = 0;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++) {
                f[i][j][0] = (a[i] != b[j]) ? INF :
                    min(f[i-1][j-1][0], f[i-1][j-1][1] + 3);
                f[i][j][1] = min(f[i-1][j][0], f[i-1][j][1]);
            }
        s = min(f[n][m][0], f[n][m][1] + 1);
        if(s >= INF) s = -1;
        printf("%d\n", s);
    }
    return 0;
}