题目大意

给定两串 DNA 序列，可以在其中任意插空格，然后逐位比较，当两位都是字母时查表得到相似度。

长度为 $k$ 的空格有额外相似度 $- A - B(k - 1)$。求两序列的最大相似度。

分析

若不考虑空格的贡献，容易想到二维 DP，记 ${\rm DP}[i,j]$ 是 $A$ 串到位置 $i$ 同时 $B$ 串到位置 $j$ 时最大的相似度，有

$$ {\rm DP}[i, j] = \max\{ {\rm DP}[i - 1, j - 1] + D[i, j], {\rm DP}[i - 1, j], {\rm DP}[i, j - 1] \} $$

当我们考虑空格的贡献时，可以发现空格的额外贡献只与前面一位有关。若两个序列此位都是空格，则把去掉后相似度一定会增加，故只有三种可能：设 ${\rm DP}_0$ 是结尾没有空格；${\rm DP}_1$ 是空格在 $A$ 串；${\rm DP}_2$ 是空格在 $B$ 串。

思考最后一个空格的转移方式，自然有方程

$$ \begin{aligned} {\rm DP}_0[i, j] &= \max\{ {\rm DP}_0[i - 1, j - 1], {\rm DP}_1[i - 1, j - 1], {\rm DP}_2[i - 1, j - 1] \} + D[i, j] \\ {\rm DP}_1[i, j] &= \max\{ {\rm DP}_0[i, j - 1] - A, {\rm DP}_1[i, j - 1]- B, {\rm DP}_2[i, j - 1] - A\} \\ {\rm DP}_2[i, j] &= \max\{ {\rm DP}_0[i - 1, j] - A, {\rm DP}_1[i - 1, j] - A, {\rm DP}_2[i, j - 1] - B \} \\ \end{aligned} $$

随手加滚动数组 WA 了好久，发现每次都要清空为 -INF，否则会 WA。

#include "template/index.hpp"

const int maxn = 3000 + 10;

int dp_1[maxn][3], dp_2[maxn][3];

char sa[maxn], sb[maxn];

int D[5][5];

int DNA(char c); // AGTC -> 1..4

int main() {
	scanf("%s %s", sa + 1, sb + 1);
	int n = strlen(sa + 1), m = strlen(sb + 1);

	for (int i = 1; i <= 4; i++)
		for (int j = 1; j <= 4; j++)
			D[i][j] = rr();

	int A = rr(), B = rr(), *p;

	memset(dp_1, -0x7f, sizeof(dp_1));
	memset(dp_2, -0x7f, sizeof(dp_2));

	auto &dp1 = dp_1, &dp2 = dp_2;
	dp2[0][0] = 0;

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			int da = DNA(sa[i]), db = DNA(sb[j]);
			if (i > 0 && j > 0) {
				p = dp1[j - 1];
				dp2[j][0] = max3(p[0], p[1], p[2]) + D[da][db];
			}
			if (i > 0) {
				p = dp1[j];
				dp2[j][2] = max3(p[0] - A, p[1] - A, p[2] - B);
			}
			if (j > 0) {
				p = dp2[j - 1];
				dp2[j][1] = max3(p[0] - A, p[1] - B, p[2] - A);
			}
		}
		swap(dp1, dp2);
		memset(dp2, -0x7f, sizeof(dp2));
	}
	p = dp1[m];
	int ans = max3(p[0], p[1], p[2]);
	printf("%d\n", ans);
	return 0;
}