POJ1699Best Sequence(DFS)

链接

这题其实是由bug的 一个串包含其它两个串的数据没有 所以就这么水了它吧 只处理两个串的关系就行了

回来补点。。看了huge的博客 发现其实不是有Bug  题意没读清楚 必须首尾相连 像AGCT GC这样就不算。。降低了复杂

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define INF 0x3f3f3f

 char s[][];

 int k[],o[][],n;

 int vis[],ans;

 void init()

 {

     int i,j;

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

     {

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

         {

             if(i==j)

             continue;

             o[i][j] = ;

             for(int g =  ; g < k[i] ; g++)

             {

                 if(s[j][]==s[i][g])

                 {

                     int k1 = ,k2 = g+;

                     while(k1<k[i]&&k2<k[j]&&s[j][k1]==s[i][k2])

                     {

                         k1++;

                         k2++;

                     }

                     if(k1==k[i]||k2==k[j])

                     {

                         o[i][j] = k1;

                         break;

                     }

                 }

             }

         }

     }

 }

 void dfs(int x,int v,int sum)

 {

     if(sum>ans)

     return ;

     if(v==n)

     {

         ans = sum;

         return ;

     }

     int i;

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

     {

         if(!vis[i])

         {

             vis[i] = ;

             sum+=(k[i]-o[x][i]);

             dfs(i,v+,sum);

             sum-=(k[i]-o[x][i]);

             vis[i] = ;

         }

     }

 }

 int main()

 {

     int i,t;

     scanf("%d",&t);

     while(t--)

     {

         memset(vis,,sizeof(vis));

         ans = INF;

         scanf("%d%*c",&n);

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

         {

             scanf("%s",s[i]);

             k[i] = strlen(s[i]);

         }

         init();

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

         {

             vis[i] = ;

             dfs(i,,k[i]);

             vis[i] = ;

         }

         printf("%d\n",ans);

     }

     return ;

 }