P1140 相似基因 动态规划

• 题目

输出基因相似度。

• 分析

这题的的DP方程很好想。

f[i][j]表示S1前i位与S2前j位对应时最大的相似度 前人的方程：

f[i][j]=max(f[i-1][j]+T[A[i]][4],
            f[i][j-1]+T[B[j]][4],
            f[i-1][j-1]+T[A[i]][B[j]]); 

个人觉得，最难受的是初始化emmm。

在初始化这里坑了很久。

一个是由于基因相似度可以为负值，所以DP的数组不能初始化为0，这个坑我避开了。

还有一个初始化条件没有想到。这两个初始化的边界，没有考虑到。

• 代码

//P1140
#include<iostream>
#include<algorithm>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<stdio.h>
#include<map>
using namespace std;
#define ll long long

//string l,s;
map<char,int> mp; 
int dp[105][105];
int s1[105];
int s2[105];
int w[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,0};
int main()
{
	int m,n;
	cin>>m;

	for(int i=1;i<=m;i++)
	{
		char ch;
		cin>>ch;
		if(ch=='A') s1[i]=0;
		if(ch=='C') s1[i]=1;
		if(ch=='G') s1[i]=2;
		if(ch=='T') s1[i]=3;
	}
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		char ch;
		cin>>ch;
		if(ch=='A') s2[i]=0;
		if(ch=='C') s2[i]=1;
		if(ch=='G') s2[i]=2;
		if(ch=='T') s2[i]=3;
	}	
	for(int i=1;i<105;i++)
	for(int j=1;j<105;j++)
		dp[i][j]=-2e8;
	
	dp[0][0]=0;	
	for(int i=1;i<=m;i++)
		dp[i][0]=dp[i-1][0]+w[s1[i]][4];
	for(int i=1;i<=n;i++)
		dp[0][i]=dp[0][i-1]+w[4][s2[i]];
	
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dp[i][j]=max(	dp[i-1][j]+w[s1[i]][4],
						max(dp[i-1][j-1]+w[s1[i]][s2[j]],
							dp[i][j-1]+w[4][s2[j]]));
		}
	}
	cout<<dp[m][n]<<endl;
	
}