洛谷P4059 找爸爸
作者:
Air1222
,
2024-04-07 14:41:02
,
所有人可见
,
阅读 6
//题目中g(k)=−A−B(k−1)的含义为第一个空格-A,连续空格大于1时,每多1就-B
//f[i][j][0/1][0/1]:
//a串已经匹配到第i个字符,b串匹配到第j个字符,且第i/j个字符可以用当前字符也可以用空格(0/1),插入可以看作当前字符用空格
//当f[i][j][0][0]时,为无意义状态,不用考虑,因为这样必无意义多加一个负数
//因为转移中存在负数,因此需要先初始化为负无穷
//较大值(int):0x3f
//较小值(int):0xc0
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 3005;
map<char,int>h;
char a[N],b[N];
int x,y;
int f[N][N][2][2];
int g[4][4];
int main()
{
h['A']=0,h['T']=1,h['G']=2,h['C']=3;
memset(f,0xcf,sizeof f);
cin>>a+1>>b+1;
int n=strlen(a+1);
int m=strlen(b+1);
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
cin>>g[i][j];
f[0][0][1][1]=0;//可以看成空字符和空字符匹配(通过下面转移方程想初始值也可以)
cin>>x>>y;
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
{
if(i) f[i][j][1][0]=max(max(f[i-1][j][1][0]-y,f[i-1][j][0][1]-x),f[i-1][j][1][1]-x);
if(j) f[i][j][0][1]=max(max(f[i][j-1][1][0]-x,f[i][j-1][0][1]-y),f[i][j-1][1][1]-x);
if(i&&j) f[i][j][1][1]=max(max(f[i-1][j-1][1][0],f[i-1][j-1][1][1]),f[i-1][j-1][0][1])+g[h[a[i]]][h[b[j]]];
}
cout<<max(max(f[n][m][1][0],f[n][m][0][1]),f[n][m][1][1]);
return 0;
}