题意：求出将两个字符串改成一样长度所能形成最大的相似度。
思路：这个可以说是编辑距离的一个变形，编辑距离最终状态时要两个字符串完全一致，这个就是要求长度一样，而且这个只允许插入“—”这一个字符。模仿编辑距离定义状态，dp[i][j]表示将第一个字符串的前i个字符与第二个字符串的前j个字符变为相同长度所能形成的最大相似度。设两个字母的相似度为g[i][j];
那状态转移为 dp[i][j] = max( dp[i][j-1] + g[j][5], d[i-1][j] + g[i][5],dp[i-1][j-1] + g[i][j] ) 前两个代表插入“—”，后一个表示直接匹配。
注意：这个题我WA了两次，在定义初始状态dp[i][0] 和 dp[0][i]时，我忘记了累加消耗，而且还过了样例……后来自己举了一个例子才修正的。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
#define N 220
map<char,int> m;
int g[N][N];
void Init();///初始化得出相似度
char a[N],b[N];
int Solve(int lena,int lenb){
int dp[N][N];
char tmpa,tmpb;
int numa,numb,sum;
memset(dp,,sizeof(dp));
sum = ;
for(int i = ;i <= lenb;i++){
tmpb = b[i];
numb = m[tmpb];
sum += g[][numb];///不要忘记消耗是累加的
dp[][i] = sum;
}
sum = ;
for(int i = ;i <= lena;i++){
tmpa = a[i];
numa = m[tmpa];
sum += g[numa][];
dp[i][] = sum;
}
for(int i = ;i <= lena;i++){
for(int j = ;j <= lenb;j++){
tmpa = a[i],tmpb = b[j];
numa = m[tmpa],numb = m[tmpb];
dp[i][j] = max(dp[i-][j]+g[numa][],dp[i][j-]+g[][numb]);
dp[i][j] = max(dp[i][j],dp[i-][j-]+g[numa][numb]);
}
}
return dp[lena][lenb];
}
void Input(){
int t,n,mm;
scanf("%d",&t);
while(t--){
scanf("%d %s",&n,a+);
scanf("%d %s",&mm,b+);
printf("%d\n",Solve(n,mm));
}
}
int main(){
// freopen("A.in.cpp","r",stdin);
Init();
Input();
return ;
}
void Init(){
m.clear();
m['A'] = ;
m['C'] = ;
m['G'] = ;
m['T'] = ;
memset(g,,sizeof(g));
for(int i = ;i <= ;i++){
g[i][i] = ;
}
g[][] = g[][] = -;
g[][] = g[][] = -;
g[][] = g[][] = -;
g[][] = g[][] = -;
g[][] = g[][] = g[][] = g[][] = -;
g[][] = g[][] = g[][] = g[][] = g[][] = g[][] = -;
g[][] = g[][] = -;
}