洛谷P1140 相似基因

今天药忘吃喽~ 2022-05-26 23:51 168阅读 0赞

## 题目背景 ##

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

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

## 题目描述 ##

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

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

![41.png][]

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

![40.png][]

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

![42.png][]

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

## 输入输出格式 ##

输入格式：

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

输出格式：

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

![70][]

思路：

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

类似于最长公共子序列

![70 1][]

但是此题有改动，每次可以选择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;
    }

[41.png]: /images/20220527/1c0bb33a1c4f49e28fcc648b1df6e97d.png
[40.png]: /images/20220527/2630717799cb49ceb63a8b90023aa212.png
[42.png]: /images/20220527/e42c7e35b4dc4b8b8a8011f07b598559.png
[70]: /images/20220527/cbe6a41d74264866861478fe48021293.png
[https_www.luogu.org_blog_2e8JR_solution-p1140]: https://www.luogu.org/blog/2e8JR/solution-p1140
[70 1]: /images/20220527/5f811c6ab08141ad94a7f7a16d755124.png