洛谷P1140 相似基因

题目背景

大家都知道，基因可以看作一个碱基对序列。它包含了4种核苷酸，简记作A,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。

在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。

题目描述

两个基因的相似度的计算方法如下：

对于两个已知基因，例如AGTGATG和GTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基-，例如：

这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：

那么相似度就是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。因为两个基因的对应方法不唯一，例如又有：

相似度为：(-3)+5+5+(-2)+5+(-1)+5=14。规定两个基因的相似度为所有对应方法中，相似度最大的那个。

输入输出格式

输入格式：

共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含A,C,G,T四个字母。1<=序列的长度<=100。

输出格式：

仅一行，即输入基因的相似度。

思路：

参考题解：https://www.luogu.org/blog/2e8JR/solution-p1140

类似于最长公共子序列

但是此题有改动，每次可以选择A[i]与空碱基配对或者B[j]与空碱基配对或者A[i]与B[j]配对，所以有三个转移方程

dp[i][j] = max(dp[i][j], dp[i - 1][j] + Map[getName(a)][getName('-')]);//此处A[i]与'-'配对
dp[i][j] = max(dp[i][j], dp[i][j - 1] + Map[getName(b)][getName('-')]);//此处B[j]与'-'配对

dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + Map[getName(a)][getName(b)]);//此处A[i]与B[j]配对

动归前要预处理，很骚啊这个。。。

#include<iostream>
#include<algorithm>
using namespace std;

int lenA;
int lenB;
char A[105];
char B[105];
int dp[105][105];
int Map[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 getName(char c)
{
	switch (c)
	{
	case 'A':return 0;
	case 'C':return 1;
	case 'G':return 2;
	case 'T':return 3;
	case '-':return 4;
	}
}

int main()
{
	//freopen("1.txt", "r", stdin);
	scanf("%d %s", &lenA, A + 1);
	scanf("%d %s", &lenB, B + 1);
    
	for (int i = 1; i <= lenA;i++)//初始化为很小的值
	for (int j = 1; j <= lenB;j++)
		dp[i][j] = -2e8;

	//此处lenA为第一段,即数组的第一维;lenB为第二段,即数组的第二维
	//第一段的1与第二段的0配对相当于与空碱基配对
	//第二段的1与第一段的0配对相当于与空碱基配对
	for (int i = 1; i <= lenA; i++) dp[i][0] = dp[i - 1][0] + Map[getName(A[i])][getName('-')];
	for (int i = 1; i <= lenB; i++) dp[0][i] = dp[0][i - 1] + Map[getName(B[i])][getName('-')];

	for (int i = 1; i <= lenA; i++)
	{
		for (int j = 1; j <= lenB; j++)
		{
			char a = A[i]; char b = B[j];
			dp[i][j] = max(dp[i][j], dp[i - 1][j] + Map[getName(a)][getName('-')]);//此处A[i]与'-'配对
			dp[i][j] = max(dp[i][j], dp[i][j - 1] + Map[getName(b)][getName('-')]);//此处B[j]与'-'配对
			dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + Map[getName(a)][getName(b)]);//此处A[i]与B[j]配对
			//cout << dp[i][j] << ' ';
		}
		//cout << '\n';
	}
	cout << dp[lenA][lenB];
	return 0;
}