洛谷题单指南-动态规划3-P1140 相似基因

原题链接：https://www.luogu.com.cn/problem/P1140

题意解读：两个只包含A、C、G、T4个字符的序列，根据已经定义好的字符-字符的相似度，计算两个序列最大的相似度，两个序列必须每个字符都配对，如果字符不够，可以插入'-'代替。

解题思路：

本题要解决几个问题:

1、状态表示

既然有两个序列，设分别为a[n]、b[m]，很容易想到设dp[i][j]表示a序列1~i和b序列1~j的相似度

为了方便查表计算字符-字符对应的相似度，可以将'A'、'C'、'G'、'T'、'-'转换为0,1,2,3,4

这样可以用二维数组保存所有的相似度关系：

int s[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
};

2、状态转移

对与a[1~i]和b[1~j]，重点考虑最后一个字符的配对关系，有三种可能：

a[i]和b[j]配对：dp[i][j] = dp[i-1][j-1] + s[a[i]][b[j]]

在a[i]后面插入'-'，用'-'和b[i]配对：dp[i][j] = dp[i][j-1] + s[4][b[j]]

在b[i]后面插入'-'，用a[i]和'-'配对：dp[i][j] = dp[i-1][j] + s[a[i]][4]

以上三种情况取max即可

3、初始化

由于i，j都从1开始枚举，而递推式中会依赖于i-1，j-1，因此要对dp[i][0]以及dp[0][i]进行初始化

dp[i][0]表示a[1~i]与空串的相似度，就是a中每个字符与'-'配对的相似度之和

dp[0][i]表示空串与b[1~i]的相似度，就是'-'与b中每个字符配对的相似度之和

dp[0][0]保持0即可，没有配对发生

4、结果

dp[n][m]

100分代码：

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

const int N = 105;
int n, m;
int a[N], b[N]; //对应两组碱基序列, A,C,G,T分别对应0,1,2,3，-对应4
int dp[N][N]; //dp[i][j]表示a序列1~i和b序列1~j的相似度
int s[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 getnum(char x)
{
    if(x == 'A') return 0;
    if(x == 'C') return 1;
    if(x == 'G') return 2;
    if(x == 'T') return 3;
    if(x == '-') return 4;
}

int main()
{
    char x;
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        a[i] = getnum(x);
    }
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x;
        b[i] = getnum(x);
    }

    for(int i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i-1][0] + s[a[i]][4]; //初始化所有的dp[i][0]为a：1~i对应'-'的相似度之和
    }
    for(int i = 1; i <= m; i++)
    {
        dp[0][i] = dp[0][i-1] + s[4][b[i]]; //初始化所有的dp[0][i]为'-'对应b：1~i的相似度之和
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            dp[i][j] = max(dp[i-1][j-1] + s[a[i]][b[j]], max(dp[i][j-1] + s[4][b[j]], dp[i-1][j] + s[a[i]][4]));
        }
    }
    cout << dp[n][m];

    return 0;
}