题解 P4059 【「CodePlus 2017 11 月赛」找爸爸】

Elegia · 2018-01-07 14:32:20 · 题解

考虑进行动态规划。

令状态dp[i][j][k]表示目前A串已经匹配了前i个字符，B串已经匹配了前j个字符，k代表是否末尾的空格位置。两个都是空格显然不是一个优解，因为把这两个都去掉就必然会使得相似度增加。

故k只有代表3种可能：没有空格/在A串/在B串。

如果此状态没有任何空格即k=0，就直接从dp[i - 1][j - 1][]中最大相似值转移。如果在其中一个位置，那么就要考虑到上一个空格的位置在哪，我们不妨认为每段空格的第一个需要支付-a的代价，后面的都需要支付-b的代价，就很自然地列出了方程dp[i][j][1] = max{dp[i][j - 1][1] - b, dp[i][j - 1][0] - a, dp[i][j - 1][2] - a}。

dp[i][j][2]的原理是对称的。

答案在dp[n][m][]中取得。

注意一些边界问题。

#include <climits>
#include <cstdio>
#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 3010;

int n, m, a, b;
int x[N], y[N], mp[256];
int d[4][4];
char s[N];

ll dp[N][N][3];

int main() {
    mp['A'] = 0;
    mp['T'] = 1;
    mp['G'] = 2;
    mp['C'] = 3;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i)
        x[i] = mp[s[i]];
    scanf("%s", s + 1);
    m = strlen(s + 1);
    for (int i = 1; i <= m; ++i)
        y[i] = mp[s[i]];
    for (int i = 0; i < 4; ++i)
        for (int j = 0; j < 4; ++j)
            scanf("%d", &d[i][j]);
    scanf("%d%d", &a, &b);
    for (int i = max(n, m); i; --i) {
        dp[0][i][0] = dp[i][0][0] = dp[0][i][2] = dp[i][0][1] = -(1LL << 60);
        dp[0][i][1] = dp[i][0][2] = -a - b * (i - 1);
    }
    dp[0][0][1] = dp[0][0][2] = -(1LL << 60);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            dp[i][j][0] = *max_element(dp[i - 1][j - 1], dp[i - 1][j - 1] + 3) + d[x[i]][y[j]];
            dp[i][j][1] = max(max(dp[i][j - 1][0] - a, dp[i][j - 1][1] - b), dp[i][j - 1][2] - a);
            dp[i][j][2] = max(max(dp[i - 1][j][0] - a, dp[i - 1][j][2] - b), dp[i - 1][j][1] - a);
        }
    printf("%lld\n", *max_element(dp[n][m], dp[n][m] + 3));
    return 0;
}