题目大意：

将两个字符串对齐（只包含ACGT,可以用'-'占位），按照对齐分数表（参见题目）来计算最后的分数之和，输出最大的和。

例如：AGTGATG 和 GTTAG ，对齐后就是（为了表达对齐，这里我用m表示'-'）

AGTGATG

mGTTAmG

题目分析：

首先看出这道题与LCS有关，下面来考虑转移：

当t1[i]==t2[j]时，和LCS一样，\(dp[i][j] = dp[i-1][j-1]+score[t1[i]][t2[j]]\)

当t1[i]!=t2[j]时，唯一不同的是这里会有3中选择：

让1_i-1和1j-1对齐，加上ij对齐的分数。
让1_i-1和1j对齐，加上i和'-'对齐的分数。
让1_i和1j-1对齐，加上j和'-'对齐的分数。

取这三者的较大值。

最后总结方程如下：

\[dp[i][j] = dp[i-1][j-1]+score[t1[i]][t2[j]] (t1[i] == t2[j])
\]

\[d[[i][j] = max(dp[i-1][j]+score[t1[i]]['-'], dp[i][j-1]+score[t2[j]]['-'], dp[i-1][j-1]+score[t1[i]][t2[j]]) (t1[i] != t2[j])
\]

code

#include <bits/stdc++.h>

using namespace std;

const int N = 150, OO = 0x3f3f3f3f;

const int score[10][10] = {{0},

                           {0, 5, -1, -2, -1, -3},

                           {0, -1, 5, -3, -2, -4},

                           {0, -2, -3, 5, -2, -2},

                           {0, -1, -2, -2, 5, -1},

                           {0, -3, -4, -2, -1, 0}

                          };

int T, len1, len2;

string s1, s2;

int t1[N], t2[N], dp[N][N];

inline int getVal(char c){

    switch(c) {

        case 'A' : return 1; break;

        case 'C' : return 2; break;

        case 'G' : return 3; break;

        case 'T' : return 4; break;

        defualt: assert(false);

    }

}

inline void init(){

    memset(dp, 0, sizeof dp);

    for(int i=1; i<=len1; i++) dp[i][0] = dp[i-1][0] + score[t1[i]][5];

    for(int i=1; i<=len2; i++) dp[0][i] = dp[0][i-1] + score[t2[i]][5];

}

int main(){

    freopen("h.in", "r", stdin);

    ios::sync_with_stdio(false);

    cin.tie(NULL), cout.tie(NULL);

    cin >> T;

    while(T--){

        cin >> len1 >> s1 >> len2 >> s2;

        for(int i=0; i<len1; i++) t1[i+1] = getVal(s1[i]);

        for(int i=0; i<len2; i++) t2[i+1] = getVal(s2[i]);

        init();

        for (int i=1; i<=len1; i++)

            for (int j=1; j<=len2; j++) {

                if(t1[i] == t2[j]) dp[i][j] = dp[i-1][j-1] + score[t1[i]][t2[j]];

                else dp[i][j] = max(dp[i - 1][j - 1] + score[t1[i]][t2[j]],

                               max(dp[i - 1][j] + score[t1[i]][5],

                                   dp[i][j - 1] + score[t2[j]][5]));

            }

        cout << dp[len1][len2] << endl;

    }

}

巴特西

HDU 1080 Human Gene Functions - 最长公共子序列（变形）

题目大意：

题目分析：

code

最新文章

热门文章