HDU 4681 STRING dp+暴力。

题意：不说了很好懂、

这题这么水= =。。。当时竟然没有勇气暴力搜一下。昨天（好吧前天。）比赛的时候胃疼，看到这题想了一个办法就是对每一个出现最短的C串前后连接然后对这个串求最长公共子序列。其实优化一下就是现在的答案啊~~！！！！给赵鹏说了赵鹏说不可能这么过。。然后就没想。就这样这么水的一道题都没过！！！！桑心啊~

代码：

 #include <iostream>

 #include <string.h>

 #include <stdio.h>

 #include <vector>

 using namespace std;

 char sa[];

 char sb[];

 char sc[];

 int c[][];

 int d[][];

 struct node

 {

     int s,e;

 };

 int main()

 {

     int t;

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

    // freopen("out1.txt","w",stdout);

    int cas;

    cas = ;

     scanf("%d",&t);

     while(t--)

     {

         vector<node>vc,vd;

         scanf("%s",sa+);

         scanf("%s",sb+);

         scanf("%s",sc+);

         int len1,len2,len3;

         len1 = strlen(sa+);

         len2 = strlen(sb+);

         len3 = strlen(sc+);

         int i,j;

         memset(c,,sizeof(c));

         memset(d,,sizeof(c));

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

         {

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

             {

                 if(sa[i] == sb[j])

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

                 else

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

             }

         }

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

         {

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

             {

                 if(sa[i] == sb[j])

                 d[i][j] = d[i+][j+]+;

                 else

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

             }

         }

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

         {

             int cnt;

             cnt = ;

             if(sa[i] == sc[])

             {

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

                 {

                     if(sa[j] == sc[cnt])

                     cnt++;

                     if(cnt > len3)

                     {

                         struct node tmp;

                         tmp.s = i,tmp.e = j;

                         vc.push_back(tmp);

                         break;

                     }

                 }

             }

         }

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

         {

             int cnt;

             cnt = ;

             if(sb[i] == sc[])

             {

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

                 {

                     if(sb[j] == sc[cnt])

                         cnt++;

                     if(cnt > len3)

                     {

                         struct node tmp;

                         tmp.s = i;tmp.e = j;

                         vd.push_back(tmp);

                         break;

                     }

                 }

             }

         }

        // printf("%d %d\n",c[len1][len2],d[1][1]);

         int f,r;

         int ans = ;

         for(i = ;i < vc.size();i++)

         {

             for(j= ;j < vd.size();j++)

             {

                 if(vc[i].s == ||vd[j].s == )

                 f = ;

                 else f = c[vc[i].s-][vd[j].s-];

                 if(vc[i].e == len1||vd[j].e == len2)

                 r = ;

                 else

                 r = d[vc[i].e+][vd[j].e+];

                 ans = max(ans,f+r+len3);

             }

            // printf("%d****\n",i);

         }

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

         //cout<<ans<<endl;

     }

     return ;

 }

巴特西

HDU 4681 STRING dp+暴力。

最新文章

热门文章