[sourcecode language='cpp']
#include
#include
int t(char first,char second)
{
if (first==second && first!=’ ‘) return 5;
else
{
if ((first==’A’ && second==’C')||(first==’C’ && second==’A')) return -1;
if ((first==’A’ && second==’G')||(first==’G’ && second==’A')) return -2;
if ((first==’A’ && second==’T')||(first==’T’ && second==’A')) return -1;
if ((first==’C’ && second==’G')||(first==’G’ && second==’C')) return -3;
if ((first==’C’ && second==’T')||(first==’T’ && second==’C')) return -2;
if ((first==’G’ && second==’T')||(first==’T’ && second==’G')) return -2;
if ((first==’A’ && second==’ ‘)||(first==’ ‘ && second==’A')) return -3;
if ((first==’C’ && second==’ ‘)||(first==’ ‘ && second==’C')) return -4;
if ((first==’G’ && second==’ ‘)||(first==’ ‘ && second==’G')) return -2;
if ((first==’T’ && second==’ ‘)||(first==’ ‘ && second==’T')) return -1;
}
if (first==’ ‘ && second==’ ‘) return 100;
}
using namespace std;
int main()
{
int times,m,n,f[101][101],a,b,c,k,i,j,I,J;
char one[101],two[101];
cin>>times;
for (k=0;k {
cin>>m;
for (i=1;i<=m;i++)cin>>one[i];
cin>>n;
for (i=1;i<=n;i++)
cin>>two[i];

for (i=0;i<=m;i++) for (j=0;j<=n;j++) f[i][j]=0;
f[0][0]=0;
for (i=1;i<=m;i++) f[i][0]=f[i-1][0]+t(one[i],' ');
for (i=1;i<=n;i++) f[0][i]=f[0][i-1]+t(' ',two[i]);

for (i=1;i<=m;i++)
{for (j=1;j<=n;j++)
{
if (one[i]!=two[j])
{
a=f[i-1][j-1]+t(one[i],two[j]);
b=f[i-1][j]+t(one[i],' ');
c=f[i][j-1]+t(' ',two[j]);
f[i][j]=a>b&amp;&amp;a>c?a:(b>c?b:c);
}
else f[i][j]=f[i-1][j-1]+t(one[i],two[j]);
}
}
cout< }
return 0;
}

[/sourcecode]

动态规划类的问题往往被归结为水题，不过这是在这题被挂上了可用动态规划解的标签之后。事实上看出最优子结构并找出重叠子结构还是比较有技巧性的，多看看理论著述会有些帮助。