题目链接：

http://poj.org/problem?id=1080

题目大意：

给两个由A、C、T、G四个字符组成的字符串，可以在两串中加入-，使得两串长度相等。

每两个字符匹配时都有个值，求怎样安排使得总的值最大，两个-不能匹配。

解题思路：

这题转化一下就是一个裸的最长公共子串问题，只不过要求匹配时长度一样。

dp[i][j]表示第一串的第前i个字符和第二串的前j个字符匹配时，能达到的最大值。

初始化时注意dp[0][j]和dp[j][0]不能为零，为相应字符与-匹配时的总和。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

//#pragma comment(linker, "/STACK:1024000000,1024000000")

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

#define Maxn 110

map<char,int>myp;

int mar[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,-INF}}; //存入值表

char sa1[Maxn],sa2[Maxn];

int a[Maxn],b[Maxn];

int dp[Maxn][Maxn];

int main()

{

   myp['A']=0,myp['C']=1,myp['G']=2,myp['T']=3,myp['-']=4; //将字符和表映射起来

   int t,len1,len2;

   scanf("%d",&t);

   while(t--)

   {

      scanf("%d%s",&len1,sa1+1);

      for(int i=1;i<=len1;i++)

         a[i]=myp[sa1[i]]; //转化成相应的代表数字

      scanf("%d%s",&len2,sa2+1);

      for(int i=1;i<=len2;i++)

         b[i]=myp[sa2[i]];

      memset(dp,-INF,sizeof(dp));

      dp[0][0]=0;

      for(int i=1;i<=len1;i++) //注意初始化时 是和-匹配

          dp[i][0]=dp[i-1][0]+mar[a[i]][4];

         // printf("i:%d j:%d %d\n",i,0,dp[i][0]);

      for(int j=1;j<=len2;j++)

         dp[0][j]=dp[0][j-1]+mar[b[j]][4];

         //printf("i:%d j:%d %d\n",0,j,dp[0][j]);

    //  putchar('\n');

      for(int i=1;i<=len1;i++)

         for(int j=1;j<=len2;j++)

         {

            int Mx=dp[i][j];

            Mx=max(Mx,dp[i-1][j-1]+mar[a[i]][b[j]]); //i-j匹配

            Mx=max(Mx,max(dp[i-1][j]+mar[a[i]][4],dp[i][j-1]+mar[b[j]][4])); //(j和i-1,i和-)匹配 (i和j-1,-和j)匹配

            Mx=max(Mx,dp[i-1][j-1]+mar[a[i]][4]+mar[b[i]][4]); //两个都匹配-

            dp[i][j]=Mx;

            //printf("i:%d j:%d %d\n",i,j,dp[i][j]);

         }

      printf("%d\n",dp[len1][len2]);

   }

   return 0;

}