最近博客更不起来...然后又（照例）犯鼻炎了唉难受。
我们首先可以预处理碱基间的权值表。然后讲读入的碱基转化为数字，就变成了“数字匹配使权值最大”的问题。我们显然可以用动态规划解决。
两个序列配对上的dp状态设计相似，以前做过一道编辑距离也是类似配对的问题。
设f[i][j]表示第一个基因当前位置到了第i个碱基，第二个基因当前位置到了第j个碱基所能得到的最大相似度。
转移：lena*lenb 而且和状态也没有什么地方可以优化了。
决策：我们可以在每一次转移的时候有3种决策：
A串留空/B串留空/AB恰好匹配
预处理：当一个串与另一个（完全）空的串匹配时显然只有一种情况，所有状态开始由他转移而来。
1 for(int i=1;i<=lenb;i++) f[0][i]=f[0][i-1]+w[b[i]][5]; 2 for(int i=1;i<=lena;i++) f[i][0]=f[i-1][0]+w[a[i]][5];
然鹅...在这被坑了，由于有负数的权值，还要再赋一个负无穷的初值，以及f[0][0]=0!!!
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 6 using namespace std; 7 8 int lena,lenb; 9 int w[6][6]; 10 int a[200],b[200],f[200][200]; 11 char A[200],B[200]; 12 13 void init() 14 { 15 for(int i=1;i<=4;i++) w[i][i]=5; 16 w[1][2]=w[2][1]=w[1][4]=w[4][1]=w[4][5]=w[5][4]=-1; 17 w[2][3]=w[3][2]=w[1][5]=w[5][1]=-3; 18 w[1][3]=w[3][1]=w[2][4]=w[4][2]=w[3][4]=w[3][5]=w[4][3]=w[5][3]=-2; 19 w[2][5]=w[5][2]=-4; 20 } 21 int main() 22 { 23 init(); 24 /*for(int i=1;i<=5;i++) 25 { 26 for(int j=1;j<=5;j++) 27 printf("%d ",w[i][j]); 28 printf(" "); 29 }*/ 30 31 scanf("%d",&lena); 32 scanf("%s",A+1); 33 for(int i=1;i<=lena;i++) 34 { 35 if(A[i]=='A') a[i]=1; 36 if(A[i]=='C') a[i]=2; 37 if(A[i]=='G') a[i]=3; 38 if(A[i]=='T') a[i]=4; 39 } 40 scanf("%d",&lenb); 41 scanf("%s",B+1); 42 for(int i=1;i<=lenb;i++) 43 { 44 if(B[i]=='A') b[i]=1; 45 if(B[i]=='C') b[i]=2; 46 if(B[i]=='G') b[i]=3; 47 if(B[i]=='T') b[i]=4; 48 } 49 memset(f,128,sizeof(f)); 50 f[0][0]=0; 51 for(int i=1;i<=lenb;i++) f[0][i]=f[0][i-1]+w[b[i]][5]; 52 /* for(int i=1;i<=lenb;i++) 53 printf("%d ",f[0][i]);*/ 54 for(int i=1;i<=lena;i++) f[i][0]=f[i-1][0]+w[a[i]][5]; 55 for(int i=1;i<=lena;i++) 56 for(int j=1;j<=lenb;j++) 57 { 58 f[i][j]=max(f[i][j],f[i-1][j]+w[a[i]][5]); 59 f[i][j]=max(f[i][j],f[i][j-1]+w[b[j]][5]); 60 f[i][j]=max(f[i][j],f[i-1][j-1]+w[a[i]][b[j]]); 61 } 62 printf("%d",f[lena][lenb]); 63 return 0; 64 }