HUST 4681 String （DP LCS变形）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4681

题目大意：给定三个字符串A,B,C 求最长的串D，要求（1）D是A的字序列（2）D是B的子序列（3）C是D的连续子序列

Sample Input

aaaaa

aaaa

abcdef

acebdf

Sample Output

Case #1: 4

Case #2: 3

Hint

For test one, D is "aaaa", and for test two, D is "acf".

分析：求A和B的LCS，正反各求一次得到dp1和dp2，然后枚举C在A,B中的起始位置和终止位置，答案为

　　max { dp1[C在A中起始位置][C在B中起始位置] + dp2[C在A中终止位置][C在D中终止位置]+C的长度 }

代码如下：

 # include<cstdio>

 # include<cstring>

 # include<iostream>

 using namespace std;

 # define MAXN

 char s1[MAXN],s2[MAXN],s3[MAXN];

 int dp1[MAXN][MAXN],dp2[MAXN][MAXN];//dp1[][]表示字符串A，B从前往后的最大公共子串，dp2[][]表示字符串A，B从后往前的最大公共子串

 int len1,len2,len3;

 int loc11[MAXN],loc12[MAXN],loc21[MAXN],loc22[MAXN];//loc11,loc12表示C在A中起始、终止位置；loc21,loc22表示C在B中起始、终止位置

 int solve(char *str,int len,int loc1[],int loc2[])

 {

     int i,j,k;

     int cnt = ;

     for(i=; i<=len; i++)

     {

         if(str[i] == s3[])

         {

             for(j=i,k=; j<=len&&k<=len3; j++)

                 if(str[j]==s3[k])

                     k++;

             if(k != len3+)

                 break;

             loc1[cnt] = i;

             loc2[cnt] = j-;

             cnt++;

         }

     }

     return cnt;

 }

 int main()

 {

     int i,j;

     int cas,T;

     scanf("%d",&T);

     for(cas=; cas<=T; cas++)

     {

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

         len1 = strlen(s1+);

         len2 = strlen(s2+);

         len3 = strlen(s3+);

         memset(dp1,,sizeof(dp1));

         for(i=; i<=len1; i++)

             for(j=; j<=len2; j++)

             {

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

                     dp1[i][j] = dp1[i-][j-] + ;

                 else

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

             }

         memset(dp2,,sizeof(dp2));

         for(i=len1; i>=; i--)

             for(j=len2; j>=; j--)

             {

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

                     dp2[i][j] = dp2[i+][j+] + ;

                 else

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

             }

         int x=solve(s1,len1,loc11,loc12);

         int y=solve(s2,len2,loc21,loc22);

         int ans=;

         for(i=; i<x; i++)

             for(j=; j<y; j++)

                 ans = max(ans, dp1[loc11[i]-][loc21[j]-] + dp2[loc12[i]+][loc22[j]+]);

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

     }

     return ;

 }

秒客网

HUST 4681 String （DP LCS变形）

相关文章