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

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

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

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

贴代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define N 1005
  5 using namespace std;
  6 char a[2][N],b[N];//a[0]为串a,a[1]为串b,b为串c
  7 int dp1[N][N],dp2[N][N];
  8 int len[3],num[2];//len[2]为串c的长度
  9 struct node
 10 {
 11     int s,e;
 12 } p[2][N];
 13 void init()//dp顺序，逆序求一次最长公共子序列
 14 {
 15     for(int i=0; i<=len[1]+1; ++i)
 16     {
 17         dp1[0][i] = 0;
 18         dp2[len[0]+1][i]=0;
 19     }
 20     for(int i=0; i<=len[0]+1; ++i)
 21     {
 22         dp1[i][0] = 0;
 23         dp2[i][len[1]+1] =0;
 24     }
 25     for(int i=1; i<=len[0]; ++i)
 26     {
 27         for(int j=1; j<=len[1]; ++j)
 28         {
 29             if(a[0][i] == a[1][j] ) dp1[i][j] = dp1[i-1][j-1]+1;
 30             else dp1[i][j] = max(dp1[i-1][j],dp1[i][j-1]);
 31         }
 32     }
 33     for(int i=len[0]; i>=1; --i)
 34     {
 35         for(int j=len[1]; j>=1; --j)
 36         {
 37             if(a[0][i]==a[1][j]) dp2[i][j]=dp2[i+1][j+1]+1;
 38             else dp2[i][j] = max(dp2[i+1][j],dp2[i][j+1]);
 39         }
 40     }
 41 }
 42 //从串中找一个包含c串的以c[0]为开始，以c[len-1]为结束的一段，记录下起始位置
 43 int pipei(int ind,int start)
 44 {
 45     int i,j=1;
 46     for(i=start+1; i<=len[ind]; ++i)
 47     {
 48         if(a[ind][i] == b[j]) ++j;
 49         if(j==len[2]) break;
 50     }
 51     if(j <len[2]) return -1;
 52     else return i;
 53 }
 54 //预处理出a串和b串中所有如上所述的子串的起始位置
 55 void yumeiju(int ind)
 56 {
 57     num[ind] = 0;
 58     for(int i=1; i<=len[ind]; ++i)
 59     {
 60         if(a[ind][i] == b[0])
 61         {
 62             int e = pipei(ind,i);
 63             if(e == -1) continue;
 64             p[ind][num[ind]].s=i;
 65             p[ind][num[ind]].e = e;
 66             ++num[ind];
 67         }
 68     }
 69 }
 70 //枚举所有的可能，求解
 71 int meiju()
 72 {
 73     init();
 74     yumeiju(0);
 75     yumeiju(1);
 76     int ans=0;
 77     for(int i=0; i<num[0]; ++i)
 78     {
 79         for(int j=0; j<num[1]; ++j)
 80         {
 81             if(dp1[p[0][i].s-1][p[1][j].s-1] + dp2[p[0][i].e+1][p[1][j].e+1] > ans)
 82                 ans = dp1[p[0][i].s-1][p[1][j].s-1] + dp2[p[0][i].e+1][p[1][j].e+1] ;
 83         }
 84     }
 85     return ans +len[2];
 86 }
 87 int main()
 88 {
 89 //    freopen("in.txt","r",stdin);
 90     int t;
 91     scanf("%d",&t);
 92     a[0][0]='#';
 93     a[1][0] ='#';
 94     for(int ser =1; ser<=t; ++ser)
 95     {
 96         scanf("%s%s%s",a[0]+1,a[1]+1,b);
 97         len[0]= strlen(a[0])-1;
 98         len[1] = strlen(a[1])-1;
 99         len[2] = strlen(b);
100         printf("Case #%d: %d
",ser,meiju());
101     }
102     return 0;
103 }

View Code

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

相关推荐