http://poj.org/problem?id=1080 (题目链接)
题意
给出两个只包含字母ACGT的字符串s1、s2，可以在两个字符串中插入字符“-”，使得s1与s2的相似度最大。
Solution
动态规划。
用f[i][j]表示字符串s1前i位和s2前j位的最大相似度，转移很简单，直接看程序吧，边界条件要注意，当i=0或j=0时，就等于是在长度等于0的字符串中全部插入“-”，使得两字符串长度相等的相似度。打个表预处理出每两个字符的相似度比较方便后面的操作。
代码
// poj1080
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi 3.1415926535898
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; int f[110][110],w[510][510],T,n1,n2;
char s1[110],s2[110]; int main() {
scanf("%d",&T);
w['A']['A']=5;w['A']['C']=-1;w['A']['G']=-2;w['A']['T']=-1;w['A']['-']=-3;
w['C']['A']=-1;w['C']['C']=5;w['C']['G']=-3;w['C']['T']=-2;w['C']['-']=-4;
w['G']['A']=-2;w['G']['C']=-3;w['G']['G']=5;w['G']['T']=-2;w['G']['-']=-2;
w['T']['A']=-1;w['T']['C']=-2;w['T']['G']=-2;w['T']['T']=5;w['T']['-']=-1;
w['-']['A']=-3;w['-']['C']=-4;w['-']['G']=-2;w['-']['T']=-1;w['-']['-']=0;
while (T--) {
memset(f,0,sizeof(f));
scanf("%d%s%d%s",&n1,s1+1,&n2,s2+1);
f[0][0]=0;
for (int i=0;i<=n1;i++) f[i][0]=w[s1[i]]['-']+f[i-1][0];
for (int i=0;i<=n2;i++) f[0][i]=w['-'][s2[i]]+f[0][i-1];
for (int i=1;i<=n1;i++)
for (int j=1;j<=n2;j++) {
f[i][j]=f[i-1][j-1]+w[s1[i]][s2[j]];
f[i][j]=max(f[i][j],f[i-1][j]+w[s1[i]]['-']);
f[i][j]=max(f[i][j],f[i][j-1]+w['-'][s2[j]]);
}
printf("%d\n",f[n1][n2]);
}
return 0;
}