题解 P2268 【[HNOI2002]DNA分子的最佳比对】

看其余两位都是直接动归，这里我来一份记忆化搜索的代码

思路跟他们相仿，这里我就不赘述了

#include<bits/stdc++.h>
#define inf 1e8
using namespace std;
int m,n,x[1105],y[1105];
char xx[1105],yy[1105];
int mem[2205][2205],mem1[2205][2205];
int dfs(int a,int s)
{
    int p,q,r,w;p=q=r=w=-inf;//因为最大值可能为负,返回值为这四种情况的最大值
    if(mem[a][s])return mem[a][s];//记忆化
    if(a>=m&&s>=n)return 0;//边界条件  
    if(a<m&&s<n&&xx[a]==yy[s]) p=1+dfs(a+1,s+1);//配对且相同
    if(a<m&&s<n&&xx[a]!=yy[s]) w=dfs(a+1,s+1);//配对但不相同
    if(s<n)q=dfs(a,s+1)-2;
    if(a<m)r=dfs(a+1,s)-2;//在左边或右边插入“-”
    mem[a][s]=max(max(p,q),max(r,w));
    return mem[a][s];
}
int main()
{
    cin>>xx>>yy;
    m=strlen(xx);
    n=strlen(yy);
    cout<<dfs(0,0);
    return 0;
}