Subsequence Pair

题意

给出两段字符串，，，设是的子序列，是的子序列，求出满足条件的子序列的总长度之和最大 ：
1.子序列：不连续的子串
2.子串：连续的一段

分析

如果要满足，那么这之中一定会有一段使得,即最长公共子序列。那么只要这个时候出现了一个位置使得,那么此时最长的满足条件的子序列就是,其中表示的是最长公共子序列

代码

#include<bits/stdc++.h>

using namespace std;

const int N=2020;

int n,m;
int f[N][N];
char a[N],b[N];

int main()
{
    while(scanf("%s%s",a+1,b+1)!=EOF)
    {
        n=strlen(a+1);m=strlen(b+1);
        for (int i=0;i<=n;i++)
            for (int j=0;j<=m;j++)
                f[i][j]=0;

        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
            {
                if(a[i]==b[j])
                    f[i][j]=max(f[i][j],f[i-1][j-1]+1);
                else
                    f[i][j]=max(f[i-1][j],f[i][j-1]);
            }

        int ans=m;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
            {
                ans=max(ans,f[i][j]*2+m-j);//单纯考虑
                if(a[i]<b[j])
                    ans=max(ans,f[i-1][j-1]*2+n-i+1+m-j+1);
            }

        printf("%d\n",ans);
    }

    return 0;
}