[文章目录]
Description
小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序列的最大相似程度。
n,m<=3000
显然不存在两个对应位置都是空格的情况，另外连续空格的代价可以看为第一个空格代价为A，其余为B。那么设三个状态，dp[i][j]表示第一个个处理完前i个，第二个处理了前j个的【1.i,j都有值; 2.i空,j有值; 3.i有值,j空; 】的最大相似度。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,f,g;
char sa[3100],sb[3100];
int a[3100],b[3100],mp[6][6];
int A[3100][3100],B[3100][3100],C[3100][3100];
inline int Max(int x,int y){return x>y ? x:y;}
int main()
{
scanf("%s%s",sa+1,sb+1);
n=strlen(sa+1); m=strlen(sb+1);
for(int i=1;i<=n;++i)
{
switch(sa[i])
{
case 'A':a[i]=1; break;
case 'T':a[i]=2; break;
case 'G':a[i]=3; break;
case 'C':a[i]=4; break;
}
}
for(int i=1;i<=m;++i)
{
switch(sb[i])
{
case 'A':b[i]=1; break;
case 'T':b[i]=2; break;
case 'G':b[i]=3; break;
case 'C':b[i]=4; break;
}
}
for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) scanf("%d",&mp[i][j]);
scanf("%d%d",&f,&g);
memset(A,0xef,sizeof A); memset(B,0xef,sizeof B); memset(C,0xef,sizeof C);
A[0][0]=0;
for(int i=0;i<=n;++i)
for(int j=0;j<=m;++j)
{
if(i&&j) A[i][j]=Max(A[i-1][j-1],Max(B[i-1][j-1],C[i-1][j-1]))+mp[a[i]][b[j]];
if(j) B[i][j]=Max(B[i][j-1]-g,Max(A[i][j-1],C[i][j-1])-f);
if(i) C[i][j]=Max(C[i-1][j]-g,Max(A[i-1][j],B[i-1][j])-f);
}
printf("%d",Max(A[n][m],Max(B[n][m],C[n][m])));
return 0;
}