提交的时候poj又挂了 忐忑了好久上不起啊
这题让我对dp的理解终于深了一点点 
这种题思路想的时候难 想到了实现代码就简单了
#include <iostream>
#include <memory.h>
using namespace std;
int getint(char x)
{
	switch(x)
	{
	case 'A':
		return 0;
	case 'C':
		return 1;
	case 'G':
		return 2;
	case 'T':
		return 3;
	case '-':
		return 4;

	}
}
int main()
{
	int values[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,-999};
	int rounds;
	int dp[101][101];
	cin>>rounds;
	while(rounds--)
	{
		memset(dp,0,sizeof(dp));
		int firstlen,secondlen;
		char first[101];
		char second[101];
		cin>>firstlen;
		for(int i=1;i<=firstlen;i++)
			cin>>first[i];
		cin>>secondlen;
		for(int i=1;i<=secondlen;i++)
			cin>>second[i];
		for(int i=1;i<=secondlen;i++)
		{
			int c=getint(second[i]);
			dp[0][i]=values[4][c]+dp[0][i-1];

		}
		for(int i=1;i<=firstlen;i++)
		{
			int c=getint(first[i]);
			dp[i][0]=values[c][4]+dp[i-1][0];
		}
		for(int i=1;i<=firstlen;i++)
		{
			for(int j=1;j<=secondlen;j++)
			{
				dp[i][j]=dp[i-1][j-1]+values[getint(first[i])][getint(second[j])];
				if(dp[i][j]<dp[i][j-1]+values[4][getint(second[j])])
					dp[i][j]=dp[i][j-1]+values[4][getint(second[j])];
				if(dp[i][j]<dp[i-1][j]+values[getint(first[i])][4])
					dp[i][j]=dp[i-1][j]+values[getint(first[i])][4];
			}
		}
		cout<<dp[firstlen][secondlen]<<endl;

	}
	return 1;
}