学步园

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

很多人都说这题比较简单，但是如果想不到方法还是不好做的，想到后基本上就等着AC了

首先要会最长公共子系列的含义，这里假设所有字符数组下标都是从1开始

第一步求串a和串b的正向最长公共子系列 dp_a[i][j]的含义是串a长度为i的前缀和串b长度为j的前缀的最长公共子系列的长度（串a从1到i的子串，和串b从1到j的字串的最长公共子系列）

第二步求出a串和b串反向的最长公共子系列dp_b[i][j]的含义是a串长度为i的后缀，和串b长度为j的后缀的最长公共子系列长度

第三步：c串在a串和b串中出现的前后位置，找到之后记录在数组中（pos_a pos_b)

第四步：枚举c在串a和串b中的位置，得出最大结果

 ans=MAX(ans,dp_a[pos_a[i][0]-1][pos_b[j][0]-1]+dp_b[pos_a[i][1]+1][pos_b[j][1]+1]);

这句代码就是第四步的核心实现，也就是现在枚举在c串在a串的第i+1个出现位置和c串在b中第j+1个出现位置

然后结果就是a串出现c位置之前和b串出现c串位置之前的最长公共子系列，加上a串出现c串位置之后和b串出现c串位置之后的最长公共子系列，然后加上c的长度（这个可以

最后在结果上加）

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define maxn 1010
#define MAX(a,b) (a>b?a:b)
char a[maxn],b[maxn],c[maxn];
int dp_a[maxn][maxn],dp_b[maxn][maxn];
int pos_a[maxn][2],pos_b[maxn][2];
int num_a,num_b;
int len_a,len_b,len_c;
int find_pos()
{
    int i,j,k;
    num_a=num_b=0;
    for(i=1;i<=len_a;i++)
    if(c[1]==a[i])
    {
        k=2;
        for(j=i+1;j<=len_a && k<=len_c;j++)
        if(c[k]==a[j])
        k++;
        if(k!=len_c+1)//这个条件如果不成立，说明现在都没找到，那么往后肯定找不到了！
        break;
        pos_a[num_a][0]=i,pos_a[num_a++][1]=j-1;//注意这里是就j-1
    }
    for(i=1;i<=len_b;i++)
    if(c[1]==b[i])
    {
        k=2;
        for(j=i+1;j<=len_b && k<=len_c;j++)
        if(c[k]==b[j])
        k++;
        if(k!=len_c+1)//这个条件如果不成立，说明现在都没找到，那么往后肯定找不到了！
        break;
        pos_b[num_b][0]=i,pos_b[num_b++][1]=j-1;//注意这里是就j-1
    }
    return 0;
}
int main()
{
    int i,j,k=0,t;
    int ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s%s",a+1,b+1,c+1);
        len_a=strlen(a+1),len_b=strlen(b+1),len_c=strlen(c+1);
        memset(dp_a,0,sizeof(dp_a));
        memset(dp_b,0,sizeof(dp_b));
        for(i=1;i<=len_a;i++)
        for(j=1;j<=len_b;j++)
        {
            if(a[i]==b[j])
            dp_a[i][j]=dp_a[i-1][j-1]+1;
            else
            dp_a[i][j]=MAX(dp_a[i-1][j],dp_a[i][j-1]);
        }

        for(i=len_a;i>=1;i--)
        for(j=len_b;j>=1;j--)
        {
            if(a[i]==b[j])
            dp_b[i][j]=dp_b[i+1][j+1]+1;
            else
            dp_b[i][j]=MAX(dp_b[i+1][j],dp_b[i][j+1]);
        }
        ans=0;
        find_pos();
        for(i=0;i<num_a;i++)
        for(j=0;j<num_b;j++)
        {
            ans=MAX(ans,dp_a[pos_a[i][0]-1][pos_b[j][0]-1]+dp_b[pos_a[i][1]+1][pos_b[j][1]+1]);
        }
        printf("Case #%d: %d\n",++k,ans+len_c);
    }
    return 0;
}