1. 题目

传送门＝￣ω￣＝

2. 题解

。。。最基础的动规题调了我一个小时。。。
。。。以后再也不在 11 点以后写题了。。。

设 $f(i,j)$为序列 1 前 $i$个字符和序列 2 前 $j$个字符产生的最大相似度。
第 $i$个字符和第 $j$个字符不一定要对齐。

设 $s(i,j)$表示字符 $i$和字符 $j$产生的相似度。
序列分别为 str1,str2。
$f(i,j)=max(f(i-1,j)+s(str1[i],-)),f(i,j-1)+s(str2[j],-),f(i-1,j-1)+s(str1[i],str2[j]))$

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,f[105][105],tab[5][5]=\
{
    {5,-1,-2,-1,-3},
    {-1,5,-3,-2,-4},
    {-2,-3,5,-2,-2},
    {-1,-2,-2,5,-1},
    {-3,-4,-2,-1,0}
};
char s1[105],s2[105];
int judge(char c)
{
    if(c=='A')return 0;
    if(c=='C')return 1;
    if(c=='G')return 2;
    if(c=='T')return 3;
}
int main()
{
    scanf("%d%s%d%s",&n,s1+1,&m,s2+1);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j]=INT_MIN;
    for(int i=1;i<=n;i++)f[i][0]=f[i-1][0]+tab[judge(s1[i])][4];
    for(int i=1;i<=m;i++)f[0][i]=f[0][i-1]+tab[judge(s2[i])][4];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=max(f[i][j],f[i][j-1]+tab[judge(s2[j])][4]),
            f[i][j]=max(f[i][j],f[i-1][j]+tab[judge(s1[i])][4]),
            f[i][j]=max(f[i][j],f[i-1][j-1]+tab[judge(s1[i])][judge(s2[j])]);
    printf("%d\n",f[n][m]);
    return 0;
}