HDU 4681 string 求最长公共子序列的简单DP+暴力枚举

先预处理，用求最长公共子序列的DP顺着处理一遍，再逆着处理一遍。

再预处理串a和b中包含串c的子序列，当然，为了使这子序列尽可能短，会以c 串的第一个字符开始 ，c 串的最后一个字符结束

将这些起始位置先记录下来，然后枚举这些位置，最大的值输出，看一下代码，你就会顿悟了····哈哈。

贴代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define N 1005

 using namespace std;

 char a[][N],b[N];//a[0]为串a,a[1]为串b,b为串c

 int dp1[N][N],dp2[N][N];

 int len[],num[];//len[2]为串c的长度

 struct node

 {

     int s,e;

 } p[][N];

 void init()//dp顺序，逆序求一次最长公共子序列

 {

     for(int i=; i<=len[]+; ++i)

     {

         dp1[][i] = ;

         dp2[len[]+][i]=;

     }

     for(int i=; i<=len[]+; ++i)

     {

         dp1[i][] = ;

         dp2[i][len[]+] =;

     }

     for(int i=; i<=len[]; ++i)

     {

         for(int j=; j<=len[]; ++j)

         {

             if(a[][i] == a[][j] ) dp1[i][j] = dp1[i-][j-]+;

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

         }

     }

     for(int i=len[]; i>=; --i)

     {

         for(int j=len[]; j>=; --j)

         {

             if(a[][i]==a[][j]) dp2[i][j]=dp2[i+][j+]+;

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

         }

     }

 }

 //从串中找一个包含c串的以c[0]为开始，以c[len-1]为结束的一段，记录下起始位置

 int pipei(int ind,int start)

 {

     int i,j=;

     for(i=start+; i<=len[ind]; ++i)

     {

         if(a[ind][i] == b[j]) ++j;

         if(j==len[]) break;

     }

     if(j <len[]) return -;

     else return i;

 }

 //预处理出a串和b串中所有如上所述的子串的起始位置

 void yumeiju(int ind)

 {

     num[ind] = ;

     for(int i=; i<=len[ind]; ++i)

     {

         if(a[ind][i] == b[])

         {

             int e = pipei(ind,i);

             if(e == -) continue;

             p[ind][num[ind]].s=i;

             p[ind][num[ind]].e = e;

             ++num[ind];

         }

     }

 }

 //枚举所有的可能，求解

 int meiju()

 {

     init();

     yumeiju();

     yumeiju();

     int ans=;

     for(int i=; i<num[]; ++i)

     {

         for(int j=; j<num[]; ++j)

         {

             if(dp1[p[][i].s-][p[][j].s-] + dp2[p[][i].e+][p[][j].e+] > ans)

                 ans = dp1[p[][i].s-][p[][j].s-] + dp2[p[][i].e+][p[][j].e+] ;

         }

     }

     return ans +len[];

 }

 int main()

 {

 //    freopen("in.txt","r",stdin);

     int t;

     scanf("%d",&t);

     a[][]='#';

     a[][] ='#';

     for(int ser =; ser<=t; ++ser)

     {

         scanf("%s%s%s",a[]+,a[]+,b);

         len[]= strlen(a[])-;

         len[] = strlen(a[])-;

         len[] = strlen(b);

         printf("Case #%d: %d\n",ser,meiju());

     }

     return ;

 }

HDU 4681 string 求最长公共子序列的简单DP+暴力枚举的相关教程结束。