一道一般的动态规划

传送门

定义式

定义一个数组di,jd_{i,j}表示第一个基因组前i个基因和第二个基因组前j个基因的最大相似度。

转移式

每一对基因都只有三种可能

  • 非空碱基与非空碱基
  • 空碱基与非空碱基
  • 非空碱基与空碱基
    这样，转移式就很清楚啦

fi,j=max(fi−1,j−1+dai,bj,fi−1,j+dai,5,fi,j−1+dbj,5)\Large{\color{black}{f_{i,j}=max(}\color{black}{f_{i-1,j-1}+d_{a_{i},b_{j}}},\color{black}{f_{i-1,j}+d_{a_{i},5}},\color{black}{f_{i,j-1}+d_{b_{j},5}}\color{black}{)}}

容易忽视的小细节

因为相似度可能是负数，所以要初始化一下

上代码

#include <bits/stdc++.h>
using namespace std;
int la,lb;
char a1[103];
char b1[103];
int a[103],b[103];
int dp[103][103];
int lena,lenb;
int v[7][7]={
	{0,0,0,0,0,0},
	{0,5,-1,-2,-1,-3},
	{0,-1,5,-3,-2,-4},
	{0,-2,-3,5,-2,-2},
	{0,-1,-2,-2,5,-1},
	{0,-3,-4,-2,-1,0},
};
int main()
{
	scanf("%d%s",&la,a1);
	scanf("%d%s",&lb,b1);
	for(int i=0;i<la;i++)
	{
		if(a1[i]=='A')
			a[i+1]=1;
		if(a1[i]=='C')
			a[i+1]=2;
		if(a1[i]=='G')
			a[i+1]=3;
		if(a1[i]=='T')
			a[i+1]=4;
	}
	for(int i=0;i<lb;i++)
	{
		if(b1[i]=='A')
			b[i+1]=1;
		if(b1[i]=='C')
			b[i+1]=2;
		if(b1[i]=='G')
			b[i+1]=3;
		if(b1[i]=='T')
			b[i+1]=4;
	}
	for(int i=1;i<=102;i++)
	{
		for(int j=1;j<=102;j++)
		{
			dp[i][j]=-1e6;
		}
	}
	for(int i=1;i<=la;i++)
		dp[i][0]=dp[i-1][0]+v[a[i]][5];
	for(int i=1;i<=lb;i++)
		dp[0][i]=dp[0][i-1]+v[5][b[i]];
	for(int i=1;i<=la;i++)
	{
		for(int j=1;j<=lb;j++)
		{
			dp[i][j]=max(dp[i][j],dp[i-1][j]+v[a[i]][5]);
			dp[i][j]=max(dp[i][j],dp[i][j-1]+v[5][b[j]]);
			dp[i][j]=max(dp[i][j],dp[i-1][j-1]+v[a[i]][b[j]]);
		}
	}
	printf("%d",dp[la][lb]);
}