【POJ1080】Human Gene Functions（动态规划）

题面：【POJ1080】Human Gene Functions

这道题目一看就能想到用DP来做。

首先，先把题中的表格放在一个函数中：

int s(char x,char y)
{
	if(x=='A')
	{
		if(y=='A') return 5;
		if(y=='C') return -1;
		if(y=='G') return -2;
		if(y=='T') return -1;
		if(y=='-') return -3;
	}
	if(x=='C')
	{
		if(y=='A') return -1;
		if(y=='C') return 5;
		if(y=='G') return -3;
		if(y=='T') return -2;
		if(y=='-') return -4;
	}
	if(x=='G')
	{
		if(y=='A') return -2;
		if(y=='C') return -3;
		if(y=='G') return 5;
		if(y=='T') return -2;
		if(y=='-') return -2;
	}
	if(x=='T')
	{
		if(y=='A') return -1;
		if(y=='C') return -2;
		if(y=='G') return -2;
		if(y=='T') return 5;
		if(y=='-') return -1;
	}
	if(x=='-')
	{
		if(y=='A') return -3;
		if(y=='C') return -4;
		if(y=='G') return -2;
		if(y=='T') return -1;
		if(y=='-') return 0;
	}
	return 0;
}

 

然后，我们要想办法推导出一个状态转移方程，这也是整个代码的核心部分。

 

我们把第一个字符串（记作s1）匹配到第i位且第二个字符串（记作s2）匹配到第j位时所能取得的最大相似度记作f[i][j]，则对于f[i][j]，它可能从3个途径得到：

①f[i][j]=f[i-1][j]+s(s1[i],'-')

②f[i][j]=f[i][j-1]+s('-',s2[j])

③f[i][j]=f[i-1][j-1]+s(s1[i],s2[j])

这应该是比较显然的，因此就不对其加以证明和解释了。

从上可知，这道题目的状态转移方程就是f[i][j]=max{f[i-1][j]+s(s1[i],'-'),f[i][j-1]+s('-',s2[j]),f[i-1][j-1]+s(s1[i],s2[j])}。

既然推出了状态转移方程，其余的就好办了，直接上代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 100
using namespace std;
int n,m,f[N+5][N+5];
string s1,s2;
int s(char x,char y)
{
	if(x=='A')
	{
		if(y=='A') return 5;
		if(y=='C') return -1;
		if(y=='G') return -2;
		if(y=='T') return -1;
		if(y=='-') return -3;
	}
	if(x=='C')
	{
		if(y=='A') return -1;
		if(y=='C') return 5;
		if(y=='G') return -3;
		if(y=='T') return -2;
		if(y=='-') return -4;
	}
	if(x=='G')
	{
		if(y=='A') return -2;
		if(y=='C') return -3;
		if(y=='G') return 5;
		if(y=='T') return -2;
		if(y=='-') return -2;
	}
	if(x=='T')
	{
		if(y=='A') return -1;
		if(y=='C') return -2;
		if(y=='G') return -2;
		if(y=='T') return 5;
		if(y=='-') return -1;
	}
	if(x=='-')
	{
		if(y=='A') return -3;
		if(y=='C') return -4;
		if(y=='G') return -2;
		if(y=='T') return -1;
		if(y=='-') return 0;
	}
	return 0;
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n),cin>>s1,scanf("%d",&m),cin>>s2;
		s1="-"+s1,s2="-"+s2;//先在s1和s2前各加一个'-' 
		for(int i=1;i<=n;i++) f[i][0]=f[i-1][0]+s(s1[i],'-');//预处理，下同 
		for(int i=1;i<=m;i++) f[0][i]=f[0][i-1]+s('-',s2[i]);
		for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=max(max(f[i-1][j]+s(s1[i],'-'),f[i][j-1]+s('-',s2[j])),f[i-1][j-1]+s(s1[i],s2[j]));//DP过程 
		printf("%d\n",f[n][m]);//输出答案 
	}
	return 0;
}

 

 

 

 

版权声明：转载请注明地址