HDU4681_String

这个题目是这样的。

给你三个字符串A，B，C，（C一定是A和B的一个公共子序列）。

现在要求你构造出一个串D，使得D同时为A和B的子序列，且C是D的一个连续子串。求D的最大可能长度。

很简单的一个DP题。

其实这个题目有三个预处理就可以搞定了。

1、f1[i][j]：A的前i个字符，B的前J个字符的最长公共子序列。

2、f2[i][j]：A的i个字符以后，B的第J个字符以后的字符的最长公共子序列。

3、A和B串以某个位置开始作为C的子序列时，最近的匹配距离（最近匹配完的那个地方）。

有了这三个预处理，剩下的只要直接暴力枚举A和B中匹配的开始位置即可。

#include <iostream>

#include <cstring>

#include <cstdio>

#define maxn 1015

using namespace std;

int f1[maxn][maxn],f2[maxn][maxn],pos1[maxn],pos2[maxn],L1,L2,L,ans,cas=,t;

char s1[maxn],s2[maxn],s[maxn];

int main()

{

    scanf("%d",&t);

    while (t--)

    {

        memset(f1,,sizeof f1);

        memset(f2,,sizeof f2);

        memset(s,,sizeof s);

        memset(pos1,,sizeof pos1);

        memset(pos2,,sizeof pos2);

        memset(s1,,sizeof s1);

        memset(s2,,sizeof s2);

        scanf("%s",s1+);scanf("%s",s2+);scanf("%s",s+);

        L1=strlen(s1+),L2=strlen(s2+),L=strlen(s+);

        for (int i=; s1[i]; i++)

            for (int j=; s2[j]; j++)

            {

                f1[i][j]=max(f1[i-][j],f1[i][j-]);

                if (s1[i]==s2[j])

                    f1[i][j]=max(f1[i][j],f1[i-][j-]+);

            }

        f2[L1+][L2]=f2[L1][L2+]=f2[L1+][L2+]=;

        for (int i=L1; i>; i--)

            for (int j=L2; j>; j--)

            {

                f2[i][j]=max(f2[i+][j],f2[i][j+]);

                if (s1[i]==s2[j])

                    f2[i][j]=max(f2[i][j],f2[i+][j+]+);

            }

        for (int i=; s1[i]; i++)

        {

            if (s1[i]!=s[])

            {

                pos1[i]=;

                continue;

            }

            int cur=,j=i;

            for (; s1[j]; j++)

            {

                if (s1[j]==s[cur]) cur++;

                if (!s[cur]) break;

            }

            if (!s[cur]) pos1[i]=j;

                else pos1[i]=;

        }

        for (int i=; s2[i]; i++)

        {

            if (s2[i]!=s[])

            {

                pos2[i]=;

                continue;

            }

            int cur=,j=i;

            for (;s2[j]; j++)

            {

                if (s2[j]==s[cur]) cur++;

                if (!s[cur]) break;

            }

            if (!s[cur]) pos2[i]=j;

                else pos2[i]=;

        }

        ans=L;

        for (int i=; s1[i]; i++)

        {

            if (pos1[i]==) continue;

            for (int j=; s2[j]; j++)

            {

                if (pos2[j]==) continue;

                ans=max(ans,L+f1[i-][j-]+f2[pos1[i]+][pos2[j]+]);

            }

        }

        printf("Case #%d: %d\n",++cas,ans);

    }

    return ;

}

巴特西

HDU4681_String

最新文章

热门文章