题面
p哥作为一名湖中医信息工程学院的同学，不仅对信息有兴趣，同时对生物也很有兴趣。相信大家从初高中生生物基本知识都知道，DNA基因可以看作一个碱基对序列。它包含了 \(4\) 种核苷酸，简记作 \(A,C,G,T\)。现在假设想计算两个基因的相似程度，相似度的计算方法如下：
对于两个已知基因，例如AGTGATG和GTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基-，例如：
| A | G | T | G | A | T | - | G |
| - | G | T | - | - | T | A | G |
这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：
| A | C | G | T | - | ||
| A | 5 | -1 | -2 | -1 | -3 | A |
| C | -1 | 5 | -3 | -2 | -4 | C |
| G | -2 | -3 | 5 | -2 | -2 | G |
| T | -1 | -2 | -2 | 5 | -1 | T |
| - | -3 | -4 | -2 | -1 | * | - |
那么相似度就是：\((-3)+5+5+(-2)+(-3)+5+(-3)+5=9\) 。但中间添加空碱基的方式不一定，因此两个基因的对应方法不唯一，例如又有：
| A | G | T | G | A | T | G |
| - | G | T | T | A | - | G |
相似度为：\((-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那方面想，题做的实在太少了
碎碎念：现在对于科研相关的一些有限的理解感觉就是，如何用有限的数据把黑的吹成白的……