【题解】洛谷P1140相似基因 线性DP

题目链接

设 $dp[i][j]$dp[i][j] 表示 $s1$s1 到 $i$i 位置，$s2$s2 到 $j$j 位置时的最大匹配值。设 $dat1[i]$dat1[i] 表示 $s1[i]$s1[i] 在匹配值数组中的对应下标，同理有 $dat2[i]$dat2[i] （空格为 $5$5），$d[i][j]$d[i][j] 表示 $i$i 和 $j$j 的匹配值。
$dp[i][j]=\max\limits_{1\leq i\leq len1,1\leq j\leq len2}\{dp[i-1][j]+d[5][dat2[j]],dp[i][j-1]+d[dat1[i]][5],dp[i-1][j-1]+d[dat1[i]][dat2[j]]\}$dp[i][j]=1≤i≤len1,1≤j≤len2max​{dp[i−1][j]+d[5][dat2[j]],dp[i][j−1]+d[dat1[i]][5],dp[i−1][j−1]+d[dat1[i]][dat2[j]]}

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s1[110],s2[110];
int len1,len2,dp[110][110],dat1[110],dat2[110],d[6][6]={{0,0,0,0,0,0},{0,5,-1,-2,-1,-3},{0,-1,5,-3,-2,-4},{0,-2,-3,5,-2,-2},{0,-1,-2,-2,5,-1},{0,-3,-4,-2,-1,0}};
int change(char s)
{
    if(s=='A')return 1;
    if(s=='C')return 2;
    if(s=='G')return 3;
    if(s=='T')return 4;
}
int main()
{
    //freopen("in.txt","r",stdin);
    memset(dp,0xcf,sizeof(dp));dp[0][0]=0;
    scanf("%d%s%d%s",&len1,s1+1,&len2,s2+1);
    for(int i=1;i<=len1;i++)
        dat1[i]=change(s1[i]);
    for(int i=1;i<=len2;i++)
        dat2[i]=change(s2[i]);
    for(int i=1;i<=len1;i++)
        dp[i][0]=dp[i-1][0]+d[dat1[i]][5];
    for(int i=1;i<=len2;i++)
        dp[0][i]=dp[0][i-1]+d[5][dat2[i]];
    for(int i=1;i<=len1;i++)
        for(int j=1;j<=len2;j++)
            dp[i][j]=max(max(dp[i][j],dp[i-1][j]+d[dat1[i]][5]),max(dp[i][j-1]+d[5][dat2[j]],dp[i-1][j-1]+d[dat1[i]][dat2[j]]));
    printf("%d\n",dp[len1][len2]);
    return 0;
}

总结

初赛归来，写道水题再睡觉qwq