【HDU - 1080】Human Gene Functions（dp，可编辑距离类问题）

题干：

给你两个DNA序列（长度不一定相同），你可以在其中任意位置上加入空格，使得最终他俩长度相同，最终相同长度的两个DNA序列会有个相似度比较（每个字符相对应的比较），问你如何放置这些空格使得总相似度最大。

题目告诉你了空格和空格比较的权值是0，这样就保证了答案的有穷性。不然如果是正数的话就可以无穷大了（本也不符合常识）

解题报告：

  类似编辑距离xjb搞就行了。dp[i][j]代表第一个序列前i个和第二个序列前j个完全匹配的最优解。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 400 + 5;
const int INF = 0x3f3f3f3f;
int sc[MAX][MAX];
int dp[MAX][MAX];
char s1[MAX],s2[MAX];
int Max(int a,int b,int c) {
	return max(a,max(b,c));
}
int main()
{
	sc['A']['A']=5;sc['C']['C']=5;sc['G']['G']=5;sc['T']['T']=5;
	sc['A']['C']=sc['C']['A']=-1;sc['A']['G']=sc['G']['A']=-2;
	sc['A']['T']=sc['T']['A']=-1;sc['C']['G']=sc['G']['C']=-3;
	sc['A'][' ']=sc[' ']['A']=-3;sc['C']['T']=sc['T']['C']=-2;
	sc['C'][' ']=sc[' ']['C']=-4;sc['G']['T']=sc['T']['G']=-2;
	sc['G'][' ']=sc[' ']['G']=-2;sc['T'][' ']=sc[' ']['T']=-1;
	int t;
	cin>>t;
	while(t--) {
		int len1,len2;
		scanf("%d%s%d%s",&len1,s1+1,&len2,s2+1);
		for(int i = 0; i<=len1; i++) 
			for(int j = 0; j<=len2; j++) dp[i][j] = -INF; 
		dp[0][0]=0;
		for(int i = 1; i<=len1; i++) dp[i][0] = dp[i-1][0] + sc[s1[i]][' '];
		for(int i = 1; i<=len2; i++) dp[0][i] = dp[0][i-1] + sc[s2[i]][' ']; 
		for(int i = 1; i<=len1; i++) {
			for(int j = 1; j<=len2; j++) {
				dp[i][j] = Max(dp[i-1][j-1]+sc[s1[i]][s2[j]],dp[i-1][j]+sc[s1[i]][' '],dp[i][j-1]+sc[s2[j]][' ']);
			}
		}	
		printf("%d\n",dp[len1][len2]);
	}


	return 0 ;
}