# include <stdio.h>
# define INVALID -999999
int len1,len2;
char c1[101],c2[101];
int dp[101][101][201];
int dic[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,INVALID};
void change(char *a)
{
     switch(*a)
     {
        case 'A':
             *a=1;
             break;
        case 'C':
             *a=2;
             break;
        case 'G':
             *a=3;
             break;
        case 'T':
             *a=4;
             break;
        };
}
int max(int a,int b,int c)
{
    int res=-99999999;
    if(a>res) res=a;
    if(b>res) res=b;
    if(c>res) res=c;
    return res;
}
    
int main()
{
    int testcase,testcase_count;
    scanf("%d",&testcase);
    for(testcase_count=1;testcase_count<=testcase;testcase_count++)
    {
        scanf("%d ",&len1);
        int i,j,k;
        for(i=1;i<=len1;i++) 
        {
           scanf("%c",c1+i);
           change(c1+i);
        }
        scanf("%d ",&len2);
        for(i=1;i<=len2;i++) 
        {
           scanf("%c",c2+i);
           change(c2+i);
        }
        /*-------------dp------------------------*/
        for(i=0;i<=len1;i++)
          for(j=0;j<=len2;j++)
            for(k=100-len2-1;k<=len1+100+1;k++)
              dp[i][j][k]=INVALID;
        dp[0][0][100]=0;
        for(i=1;i<=len1;i++)
        {
          int sum=0;
          for(j=1;j<=i;j++) sum+=dic[c1[j]][5];
          dp[i][0][100+i]=sum;
        }
        for(i=1;i<=len2;i++)
        {
          int sum=0;
          for(j=1;j<=i;j++) sum+=dic[c2[j]][5];
          dp[0][i][100-i]=sum;
        }
        for(i=1;i<=len1;i++)
         for(j=1;j<=len2;j++)
          for(k=100-len2;k<=100+len1;k++)
          {
            dp[i][j][k]=max(dp[i-1][j-1][k]+dic[c1[i]][c2[j]],
                            dp[i][j-1][k+1]+dic[5][c2[j]],
                            dp[i-1][j][k-1]+dic[c1[i]][5]
                            );
        
          }
          /*------------------------end of dp------------------------*/
          printf("%d\n",dp[len1][len2][100+len1-len2]);
    }
    return 0;
}
        
          
           
        
        

• Re:大家帮忙看看，第三维是不是有办法可以省掉?这个是记录当前状态第一个串和第二个串的长度差的 (2512) yzhw 2009-04-26 16:26:11
• Re:事实证明，本人脑袋被驴T了。。。。。 (2215) yzhw 2009-04-26 17:04:32