ZOJ 1027
/*
zoj 1027 poj 1080 思路：
三种状态,取最大值：
s1[i]和s2[j]配 ：dp[i-1][j-1]+cost[my[s1[i]]][my[s2[j]]];
s1[i]和‘-‘ 配： dp[i-1][j]+cost[my[s1[i]]][my[‘-‘]];
s2[j]和‘-‘ 配： dp[i][j-1]+cost[my[‘-‘]][my[s2[j]]];
注意边界：
d[i][0]= cost[my[s1[i]]][my[‘-‘]]+dp[i-1][0]; 只能全部和‘-‘配，
同理： dp[0][j]=cost[my[‘-‘]][my[s2[j]]]+dp[0][j-1];
*/

#include <iostream>
#include <map>
#include <cstring>
#include <string>
using namespace std;
int cost[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,-100000005}};
int dp[1005][1005];
string s1,s2;
map<char,int> my;
int main(int argc, char *argv[])
{
int t,i,n,j,m;
my[‘A‘]=0; my[‘C‘]=1; my[‘G‘]=2; my[‘T‘]=3; my[‘-‘]=4;
cin>>t;
while(t--)
{
cin>>n>>s1>>m>>s2;
s1=‘0‘+s1; s2=‘0‘+s2;
dp[0][0]=0;
for(i=1;i<=n;i++)
dp[i][0]=cost[my[s1[i]]][my[‘-‘]]+dp[i-1][0];
for(j=1;j<=m;j++)
dp[0][j]=cost[my[‘-‘]][my[s2[j]]]+dp[0][j-1];
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
int t1,t2,t3;
t1=dp[i-1][j-1]+cost[my[s1[i]]][my[s2[j]]];
t2=dp[i-1][j]+cost[my[s1[i]]][my[‘-‘]];
t3=dp[i][j-1]+cost[my[‘-‘]][my[s2[j]]];
t1=max(t1,t2); t1=max(t1,t3);
dp[i][j]=t1;
}
cout<<dp[n][m]<<endl;
}
return 0;
}