D. 相似基因 - 2023HBUCM程序设计竞赛

题面

p哥作为一名湖中医信息工程学院的同学，不仅对信息有兴趣，同时对生物也很有兴趣。相信大家从初高中生生物基本知识都知道，DNA基因可以看作一个碱基对序列。它包含了 \(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\)。
输出：仅一行，即输出基因的相似度。

题解

复习一下闫式dp分析法：AcWing 2. 01背包问题
集合：\(a\) 串的前 \(i\) 个碱基 + \(b\) 串的前 \(j\) 个碱基；
属性：要求最大相似度，即为最大价值问题。
划分方案：对于任意一对碱基，有且仅有以下三种情况：

• 非空碱基和非空碱基
• 非空碱基和空碱基
• 空碱基和非空碱基

本题状态转移的关键点：只需要考虑最后一对碱基，逐步缩小问题规模。
状态转移方程：\(f_{i,j}=max(f_{i-1,j-1}+d_{ai,bj},f_{i-1,j}+d_{ai,空},f_{i,j-1}+d_{bj,空})\)
其中 \(d\) 表示两个碱基之间的相似程度。
边界问题：\(f_{i,0}=f_{i-1,0}+d_{ai,空}\)，\(f_{0,j}=f_{0,j-1}+d_{bi,空}\)
考虑问题规模变小到极限的情况，此处为碱基串首/尾未对齐，与空串匹配的情况。

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
int n, m, f[N][N];
string a, b;

//建立相似度对应关系，也可以使用矩阵
int sim(char a, char b) {
	if (a == b)	return 5;
	if ((a == 'A' && b == 'C') || (a == 'C' && b == 'A')) return -1;
	if ((a == 'A' && b == 'T') || (a == 'T' && b == 'A')) return -1;
	if ((a == 'A' && b == 'G') || (a == 'G' && b == 'A')) return -2;
	if ((a == 'C' && b == 'G') || (a == 'G' && b == 'C')) return -3;
	if ((a == 'C' && b == 'T') || (a == 'T' && b == 'C')) return -2;
	if ((a == 'T' && b == 'G') || (a == 'G' && b == 'T')) return -2;
	if (a == 'A' && b == '0') return -3;
	if (a == 'C' && b == '0') return -4;
	if (a == 'G' && b == '0') return -2;
	if (a == 'T' && b == '0') return -1;
	return -100;
}

int main()
{
	cin >> n >> a >> m >> b;
	//优先处理边界问题
	for (int i = 1; i <= n; i++)
		f[i][0] = f[i - 1][0] + sim(a[i - 1], '0');
	for (int i = 1; i <= m; i++)
		f[0][i] = f[0][i - 1] + sim(b[i - 1], '0');
	//状态转移方程
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			f[i][j] = max({ f[i - 1][j - 1] + sim(a[i - 1], b[j - 1]), f[i - 1][j] + sim(a[i - 1], '0'), f[i][j - 1] + sim(b[j - 1], '0') });
	cout << f[n][m];
}

蒟蒻有(fei)话说：非常贴近实际的一道题，虽然当场没能出（该打）但是看到还是忍俊不禁了
当时第一反应想到的是一些字符串匹配问题，完全没往dp那方面想，题做的实在太少了
碎碎念：现在对于科研相关的一些有限的理解感觉就是，如何用有限的数据把黑的吹成白的……