题目大意是：给定两组DNA序列，要你求出它们的最大相似度
每个字母与其他字母或自身和空格对应都有一个打分，求在这两个字符串中插入空格，让这两个字符串的匹配分数最大
/* 思路是很好想的，设f[i][j]为A染色体前i个基因和B染色体前j个基因匹配的最大值 第一次测样例WA了一把，f又没有赋最小值，今天第二次了，幸亏样例测出来了，不然又要WA一次。 */ #include<cstdio> #include<iostream> #include<cstring> #define N 110 using namespace std; int a[N],b[N],f[N][N],n,m; int v[5][5]={{5,-1,-2,-1,-3}, {-1,5,-3,-2,-4}, {-2,-3,5,-2,-2}, {-1,-2,-2,5,-1}, {-3,-4,-2,-1,0}}; void work() { scanf("%d",&n); for(int i=1;i<=n;i++) { char c;cin>>c; if(c=='A')a[i]=0; if(c=='C')a[i]=1; if(c=='G')a[i]=2; if(c=='T')a[i]=3; } scanf("%d",&m); for(int i=1;i<=m;i++) { char c;cin>>c; if(c=='A')b[i]=0; if(c=='C')b[i]=1; if(c=='G')b[i]=2; if(c=='T')b[i]=3; } f[0][0]=0; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) { if(i)f[i][j]=max(f[i][j],f[i-1][j]+v[a[i]][4]); if(j)f[i][j]=max(f[i][j],f[i][j-1]+v[4][b[j]]); if(i&&j)f[i][j]=max(f[i][j],f[i-1][j-1]+v[a[i]][b[j]]); } printf("%d ",f[n][m]); } int main() { freopen("jh.in","r",stdin); int T;scanf("%d",&T); while(T--) { memset(f,466,sizeof(f)); work(); } return 0; }