---
title: Luogu-1140-相似基因
date: 2019-10-16 08:30:00
tags:
- dp
categories: ACM
---
大家都知道，基因可以看作一个碱基对序列。它包含了 $44$ 种核苷酸，简记作 $A,C,G,T$ 。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。
在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。
<!--more-->
两个基因的相似度的计算方法如下：
对于两个已知基因，例如 $AGTGATG$ 和 $GTTAG$ ，将它们的碱基互相对应。当然，中间可以加入一些空碱基 $-$ ，例如：
这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：
那么相似度就是：$(-3) + 5 + 5 + (-2) + (-3) + 5 + (-3) + 5= 9$。因为两个基因的对应方法不唯一，例如又有：
相似度为：$(-3) + 5 + 5 + (-2) + 5 + (-1) + 5 = 14$。规定两个基因的相似度为所有对应方法中，相似度最大的那个。
## 题目链接
[Luogu-1140-相似基因](https://www.luogu.org/problem/P1140)
## 输入输出格式
### 输入格式：
共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含 $A,C,G,T$ 四个字母。$1 \le$ 序列的长度$\le 100$
### 输出格式：
仅一行，即输入基因的相似度。
## 输入输出样例
### 输入样例：
7 AGTGATG
5 GTTAG
### 输出样例：
14
## 题解
看完这个题，完全没思路，想着看题解寻求一些帮助吧，看完题解还是***不会。又多看了两篇，尽量描述懂吧(好留给后面我自己看)。
首先这是一道很明显的 $dp$ ，定义 $dp[i][j]$ 代表第一个序列的前 $i$ 个碱基，与第二个序列的前 $j$ 个碱基的最大值
例如：
> 7 AGTGATG
> 5 GTTAG
> $dp[2][3]$ 代表的就是 $AG$ 与 $GTT$ 相对应的最大值
dis(i，j)表示a[i] 与 b[j] 的相似度
关于状态转移方程的定义：
1. $dp[i][j] = max(dp[i][j],dp[i-1][j-1] + dis(i,j))$
2. $dp[i][j] = max(dp[i][j],dp[i-1][j] + dis(i,4))$
3. $dp[i][j] = max(dp[i][j],dp[i][j-1] + dis(j,4))$
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 5;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int a[MAXN],b[MAXN];
int dp[MAXN][MAXN];
int n,m;
string s1,s2;
const int tab[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}
};
void init(){
for(int i = 1;i <= n;i++){
if(s1[i-1] == 'A')
a[i] = 0;
else if(s1[i-1] == 'C')
a[i] = 1;
else if(s1[i-1] == 'G')
a[i] = 2;
else
a[i] = 3;
}
for(int i = 1;i <= m;i++){
if(s2[i-1] == 'A')
b[i] = 0;
else if(s2[i-1] == 'C')
b[i] = 1;
else if(s2[i-1] == 'G')
b[i] = 2;
else
b[i] = 3;
}
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
dp[i][j] = -INF;
for(int i = 1;i <= n;i++)
dp[i][0] = dp[i-1][0] + tab[a[i]][4];
for(int i = 1;i <= m;i++)
dp[0][i] = dp[0][i-1] + tab[4][b[i]];
}
int main() {
ios::sync_with_stdio(false);
int n,m;
string s1,s2;
cin >> n >> s1 >> m >> s2;
init();
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
dp[i][j] = max(dp[i][j],dp[i][j-1] + tab[b[j]][4]);
dp[i][j] = max(dp[i][j],dp[i-1][j] + tab[a[i]][4]);
dp[i][j] = max(dp[i][j],dp[i-1][j-1] + tab[a[i]][b[j]]);
}
}
cout << dp[n][m] << endl;
return 0;
}
```
Luogu-1140-相似基因