https://www.luogu.org/problemnew/show/P1140

根据题目给出的碱基配对表，发现：

1.两基因相同时产生+5，其余都是负数。

2.任意两个不同基因相配，直接配要好于分别与空碱基配。但是两基因不满足上1点的长度不同，所以必须有一些基因与空碱基相配。

设f(i,j)表示第一个基因前i个和第二个基因前j个相配的最大相似度

边界为f(0,j)=第二个基因前j个分别与空基因相配的相似度

     f(i,0)=第一个基因前i个分别与空基因相配的相似度

f(i,j)=      f(i-1,j-1)+5    ,a[i]==b[j]

              max(    f(i-1,j)+a[i]配空 ，f(i,j-1)+b[j]配空 ，f(i-1,j-1)+a[i]配b[j]    )   ，a[i]!=b[j]

 

#include<bits/stdc++.h>
using namespace std;

int n,m,d[105][105];
char a[105],b[105]; 
map<char,int>score;
int score2[300][300];

void init()
{
	score['T']=-1;
	score['G']=-2;
	score['A']=-3;
	score['C']=-4;
	score2['A']['C']=-1;
	score2['A']['T']=-1;
	score2['A']['G']=-2;
	score2['T']['C']=-2;
	score2['T']['G']=-2;
	score2['C']['G']=-3;
}

int main()
{
	freopen("input.in","r",stdin);
	scanf("%d%s%d%s",&n,a+1,&m,b+1);
	init();   
	int sum=0;
	for(int j=1;j<=m;j++)
	{
		sum+=score[b[j]];
		d[0][j]=sum;
	}
	sum=0;
	for(int j=1;j<=n;j++)
	{
		sum+=score[a[j]];
		d[j][0]=sum;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{  
			if(a[i]==b[j])d[i][j]=d[i-1][j-1]+5;
			else d[i][j]=max(d[i-1][j-1]+min(score2[a[i]][b[j]],score2[b[j]][a[i]]),max(d[i-1][j]+score[a[i]],d[i][j-1]+score[b[j]]));
		}
	}
	cout<<d[n][m]<<endl;
	return 0;
}