Luogu-1140-相似基因

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

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

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

Alt text

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

Alt text

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

Alt text

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

题目链接

Luogu-1140-相似基因

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例：

7 AGTGATG
5 GTTAG

输出样例：

题解

看完这个题，完全没思路，想着看题解寻求一些帮助吧，看完题解还是***不会。又多看了两篇，尽量描述懂吧(好留给后面我自己看)。

首先这是一道很明显的 $dp$ ，定义 $dp[i][j]$ 代表第一个序列的前 $i$ 个碱基，与第二个序列的前 $j$ 个碱基的最大值
例如：

7 AGTGATG
5 GTTAG
$dp[2][3]$ 代表的就是 $AG$ 与 $GTT$ 相对应的最大值
dis(i，j)表示a[i] 与 b[j] 的相似度
关于状态转移方程的定义：

$dp[i][j] = max(dp[i][j],dp[i-1][j-1] + dis(i,j))$
$dp[i][j] = max(dp[i][j],dp[i-1][j] + dis(i,4))$
$dp[i][j] = max(dp[i][j],dp[i][j-1] + dis(j,4))$

代码

#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;
}