题目描述
给出两个基因串，你需要在其中插入任意个空格，使得两个串长度相同。如果两个串的某同一位置都是字母则获得某给定收益，对于每个串的每个长度为k的连续空格段要付出a(k-1)+b的损失。求最大净收益。
输入
输入第1行一个字符串，表示小A的DNA序列。
输入第2行一个字符串，表示小B的DNA序列。
接下来4行，每行4个整数，用空格隔开，表示d数组，
具体顺序如下所示。
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，意义如题中所述。
对于所有测试点
有0<B<A≤1000,-1000≤d(x,y)≤1000,d(x,y)=d(y,x)，
序列只包含{A,T,G,C}四种字符。
N+M<=3000
输出
输出共一行，表示两个序列的最大相似程度
样例输入
ATGG
ATCC
5 -4 -4 -4
-4 5 -4 -4
-4 -4 5 -4
-4 -4 -4 5
2 1
样例输出
4
题解
dp
显然空格匹配空格是血亏的，所以一定不会有两个位置都是空格。
于是可以分别设 $f[i][j],g[i][j],h[i][j]$ 表示第一个串匹配到 $i$ ，第二个串匹配到 $j$ ，最后为 空格&字母/字母&空格/字母&字母 的最大收益。
那么直接枚举 $i$ 和 $j$ 转移即可。
注意一下边界问题。
时间复杂度 $O(nm)$
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 3010
#define val(c) (c == 'A' ? 0 : c == 'T' ? 1 : c == 'G' ? 2 : 3)
using namespace std;
int v[4][4] , f[N][N] , g[N][N] , h[N][N];
char A[N] , B[N];
int main()
{
int n , m , i , j , p , q;
scanf("%s%s" , A + 1 , B + 1) , n = strlen(A + 1) , m = strlen(B + 1);
for(i = 0 ; i < 4 ; i ++ )
for(j = 0 ; j < 4 ; j ++ )
scanf("%d" , &v[i][j]);
scanf("%d%d" , &p , &q);
memset(f , 0xc0 , sizeof(f));
memset(g , 0xc0 , sizeof(g));
memset(h , 0xc0 , sizeof(h));
f[0][1] = g[1][0] = -p , h[0][0] = 0;
for(i = 2 ; i <= m ; i ++ ) f[0][i] = f[0][i - 1] - q;
for(i = 2 ; i <= n ; i ++ ) g[i][0] = g[i - 1][0] - q;
for(i = 1 ; i <= n ; i ++ )
{
for(j = 1 ; j <= m ; j ++ )
{
f[i][j] = max(f[i][j - 1] - q , max(g[i][j - 1] , h[i][j - 1]) - p);
g[i][j] = max(max(f[i - 1][j] , h[i - 1][j]) - p , g[i - 1][j] - q);
h[i][j] = max(max(f[i - 1][j - 1] , g[i - 1][j - 1]) , h[i - 1][j - 1]) + v[val(A[i])][val(B[j])];
}
}
printf("%d
" , max(max(f[n][m] , g[n][m]) , h[n][m]));
return 0;
}