P4059找爸爸

题目描述

小 A 最近一直在找自己的爸爸，用什么办法呢，就是 DNA 比对。

小 A 有一套自己的 DNA 序列比较方法，其最终目标是最大化两个 DNA 序列的相似程度，具体步骤如下：

1. 给出两个 DNA 序列，第一个长度为 $n$，第二个长度为 $m$。

2. 在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同

3. 逐位进行匹配，如果两个序列相同位置上的字符都不是空格，假设第一个是 $x$，第二个是 $y$，那么他们的相似程度由 $d(x,y)$ 定义。对于两个序列中任意一段极长的长度为 $k$ 的连续空格，我们定义这段空格的相似程度为 $g(k)=-A-B(k-1)$。

那么最终两个序列的相似程度就是所有的 $d(x,y)$ 加上所有的极长空格段的相似程度之和。

现在小 A 通过某种奥妙重重的方式得到了小 B 的 DNA 序列中的一段，他想请你帮他算一下小 A 的 DNA 序列和小 B 的 DNA 序列的最大相似程度。

输入格式

输入第 $1$ 行一个字符串，表示小 A 的 DNA 序列。

输入第 $2$ 行一个字符串，表示小 B 的 DNA 序列。

接下来 $4$ 行，每行 $4$ 个整数，用空格隔开，表示 $d$ 数组，具体顺序如下所示。

$0<B<A\le 1000,-1000\le d(x,y)\le 1000,d(x,y)=d(y,x)$，序列只包含 $A,T,G,C$ 四种字符。

d(A,A) d(A,T) d(A,G) d(A,C)
d(T,A) d(T,T) d(T,G) d(T,C)
d(G,A) d(G,T) d(G,G) d(G,C)
d(C,A) d(C,T) d(C,G) d(C,C)

最后一行两个用空格隔开的正整数 $A,B$，意义如题中所述。

输出格式

输出共一行，表示两个序列的最大相似程度。

Solution

DP

(没搞懂怎么转移的)

int x1[3010], x2[3010], d[4][4];
ll dp[3010][3010][3];
void solve() {
    map<char, int> mp;mp['A'] = 0, mp['T'] = 1, mp['G'] = 2, mp['C'] = 3;
    string s1, s2;cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();s1 = ' ' + s1;s2 = ' ' + s2;
    for (int i = 1;i <= n;i++)x1[i] = mp[s1[i]];
    for (int i = 1;i <= m;i++)x2[i] = mp[s2[i]];
    for (int i = 0;i < 4;i++)
        for (int j = 0;j < 4;j++)
            cin >> d[i][j];
    int a, b;cin >> 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] = -1e18;
        dp[0][i][1] = dp[i][0][2] = -a - b * (i - 1);
    }
    dp[0][0][1] = dp[0][0][2] = -1e18;
    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[x1[i]][x2[j]];
            dp[i][j][1] = max({dp[i][j - 1][0] - a, dp[i][j - 1][1] - b, dp[i][j - 1][2] - a});
            dp[i][j][2] = max({dp[i - 1][j][0] - a, dp[i - 1][j][2] - b, dp[i - 1][j][1] - a});
        }
    }
    cout << *(max_element(dp[n][m], dp[n][m] + 3)) << '\n';
}