本题是一道DP问题，字符串匹配问题。有3种子问题。
1.a[i]与'-'匹配；2.b[j]与'-'匹配；3.a[i]与b[j]匹配。
所以状态转移方程有 dp[i][j]=max(dp[i-1][j-1]+dir[a[i]][b[j]],max(dp[i-1][j]+dir[a[i]][4],dp[i][j-1]+dir[b[j]][4]));
如果无法理解，请参考算法导论关于DP的章节。
注意初始化。
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 using namespace std; 5 int dir[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,1}}; 6 string a_str; 7 string b_str; 8 int a[100+10]; 9 int b[100+10]; 10 int dp[100+10][100+10]; 11 void change(string aa,int n,int bb[]) //将基因串转化为数字串，方便下面计算 12 { 13 for(int i=1;i<=n;++i) 14 { 15 if(aa[i-1]=='A') bb[i]=0; 16 if(aa[i-1]=='C') bb[i]=1; 17 if(aa[i-1]=='G') bb[i]=2; 18 if(aa[i-1]=='T') bb[i]=3; 19 } 20 return; 21 } 22 int main() 23 { 24 int t,n,i,j,al,bl; 25 while(cin>>t) 26 { 27 while(t--) 28 { 29 for(i=0;i<=100;++i) //初始化 30 memset(dp[i],0,sizeof(dp[i])); 31 32 cin>>al>>a_str; 33 cin>>bl>>b_str; 34 change(a_str,al,a); //将字符串转化为数字串 35 change(b_str,bl,b); 36 37 for(i=1;i<=al;++i) 38 { 39 dp[i][0]=dir[a[i]][4]+dp[i-1][0]; 40 } 41 for(i=1;i<=bl;++i) 42 { 43 dp[0][i]=dir[b[i]][4]+dp[0][i-1]; 44 } 45 46 for(i=1;i<=al;++i) 47 { 48 for(j=1;j<=bl;++j) 49 { 50 dp[i][j]=max(dp[i-1][j-1]+dir[a[i]][b[j]],max(dp[i-1][j]+dir[a[i]][4],dp[i][j-1]+dir[b[j]][4])); 51 } 52 } 53 cout<<dp[al][bl]<<endl; 54 } 55 } 56 return 0; 57 }