洛谷P4059 找爸爸
作者:
Air1222
,
2024-04-07 14:41:02
,
所有人可见
,
阅读 6
#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;
}