POJ 1080 基因序列相似度计算 动态规划

本题为典型的动态规划，关键找出序列比对的3个不同情况，即子问题

设d[i][j]为取s1第i个字符，s2第j个字符时的最大分值

则决定p为最优的情况有三种 p数组为分数矩阵

1、 s1取第i个字母，s2取“ - ”： d[i-1][j]+p[ s1[i-1] ]['-'];

2、 s1取“ - ”，s2取第j个字母：d[i][j-1]+p['-'][ s2[j-1] ];

3、 s1取第i个字母，s2取第j个字母：d[i-1][j-1]+p[ s1[i-1] ][ s2[j-1] ];

即dp[i][j]为上述三种情况的最大值

易犯错误

1、p数组的初始化，不细心的话容易犯错（因为这个低级错误WA两次- -）

2、d[0][j],d[i][0],d[0][0]边界值的赋值

Source Code

Problem: 1080		User: yangliuACMer
Memory: 568K		Time: 0MS
Language: C++		Result: Accepted

#include <iostream>
using namespace std;
#define maxlen 200
#define MININF -1;

int max3(int x, int y, int z){
	int a = x>y?x:y;
	return a>z?a:z;
}

int main(){
	int p[maxlen][maxlen], d[maxlen][maxlen];
	char s1[maxlen], s2[maxlen];
	int len1,len2,T,i,j;

	p['A']['A']=5;//表格的初始化一定要细心，不要因为表格输入错误而WA  
    p['C']['C']=5;  
    p['G']['G']=5;  
    p['T']['T']=5;  
    p['-']['-']=MININF;  
    p['A']['C']=p['C']['A']=-1;  
    p['A']['G']=p['G']['A']=-2;  
    p['A']['T']=p['T']['A']=-1;  
    p['A']['-']=p['-']['A']=-3;  
    p['C']['G']=p['G']['C']=-3;  
    p['C']['T']=p['T']['C']=-2;  
    p['C']['-']=p['-']['C']=-4;  
    p['G']['T']=p['T']['G']=-2;  
    p['G']['-']=p['-']['G']=-2;  
    p['T']['-']=p['-']['T']=-1;

	cin>>T;
	while(T--){
		cin>>len1>>s1>>len2>>s2;
		memset(d, 0, sizeof(d));
		for(i = 1; i <= len1; i++){
			d[i][0] = d[i-1][0] + p[s1[i-1]]['-'];
		}
		for(i = 1; i < len2; i++){
			d[0][i] = d[0][i-1] + p['-'][s2[i-1]];
		}
		for(i = 1; i <= len1; i++){
			for(j = 1;j <= len2; j++){
				d[i][j] = max3(d[i-1][j-1] + p[s1[i-1]][s2[j-1]], 
					           d[i][j-1] + p['-'][s2[j-1]], 
							   d[i-1][j] + p[s1[i-1]]['-']);
			}
		}
		cout<<d[len1][len2]<<endl;
	}
	return 0;
}