題目大意：
給兩個由A、C、T、G四個字符組成的字符串，可以在兩串中加入-，使得兩串長度相等。
每兩個字符匹配時都有個值，求怎樣安排使得總的值最大，兩個-不能匹配。
解題思路：
這題轉化一下就是一個裸的最長公共子串問題，只不過要求匹配時長度一樣。
dp[i][j]表示第一串的第前i個字符和第二串的前j個字符匹配時，能達到的最大值。
初始化時注意dp[0][j]和dp[j][0]不能為零，為相應字符與-匹配時的總和。
代碼：
<SPAN style="FONT-SIZE: 14px">#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;
}
</SPAN>
