英文的一开始没看懂题。baidu一下看了别人的翻译才知道是很简单的一道动规题 和算法书里的最长公共子序列很类似 题目意思是两个字符串si和sk，每个字符匹配都有一个权值，要求他们的最大匹配权值 f[i][j]表示串A前I个字符和串B前J个字符匹配的最大权值。则有状态转移方程： f[i][j]=max{f[i-1][j-1]+stand[a[i]][b[j]],f[i-1][j]+stand[a[i]][5],f[i][j-1]+stand[5][b[j]]}; 程序如下： #include<stdio.h>int stand[6][6]={{0,0,0,0,0,0},     {0,5,-1,-2,-1,-3},     {0,-1,5,-3,-2,-4},     {0,-2,-3,5,-2,-2},     {0,-1,-2,-2,5,-1},     {0,-3,-4,-2,-1,-100000}};char ch;int f[105][105];int a[105],b[105];int main(){ int N,n1,n2,i,j; scanf("%d",&N); while(N--) {  scanf("%d%c",&n1,&ch);  for(i=1;i<=n1;i++)  {   scanf("%c",&ch);   if(ch=='A') a[i]=1;   else if(ch=='C') a[i]=2;   else if(ch=='G') a[i]=3;   else if(ch=='T') a[i]=4;  }  scanf("%d%c",&n2,&ch);  for(i=1;i<=n2;i++)  {   scanf("%c",&ch);   if(ch=='A') b[i]=1;   else if(ch=='C') b[i]=2;   else if(ch=='G') b[i]=3;   else if(ch=='T') b[i]=4;  }  f[0][0]=0;  for(i=1;i<=n1;i++)  {   f[i][0]=f[i-1][0]+stand[a[i]][5];  }  for(i=1;i<=n2;i++)  {   f[0][i]=f[0][i-1]+stand[5][b[i]];  }  for(i=1;i<=n1;i++)  {   for(j=1;j<=n2;j++)   {    f[i][j]=f[i-1][j-1]+stand[a[i]][b[j]];    if(f[i-1][j]+stand[a[i]][5]>f[i][j])     f[i][j]=f[i-1][j]+stand[a[i]][5];    else if(f[i][j-1]+stand[5][b[j]]>f[i][j])     f[i][j]=f[i][j-1]+stand[5][b[j]];   }  }  printf("%d\n",f[n1][n2]); } return 0;}

评论