1699Best Sequence

超时了啊

我的代码

#include "iostream"
#include "string.h"
#include "algorithm"
using namespace std;
char dir[4]={'C','G','A','T'};
int set[110],MIN,end,n;
char aim[110],map[110][6];

int min(int a,int b){return a>b?b:a;}
void dfs(int a){
   int flag=0,i,j;
   for(i=1;i<=n;i++){
     if(!set[i])flag=1;
   }
   if(flag==0){
     MIN=min(MIN,end);
     return;
   }
   //for(i=1;i<=end;i++)cout<<aim[i]<<' ';cout<<endl;system("pause");

   flag=0;
   for(i=1;i<=n;i++){
     if(!set[i]){
       int ans=0;
       int tem=min(end,a+3);
       for(j=a;j<=tem;j++){
         if(aim[j]!=map[i][j-a+1])ans=1;
       }
       if(!ans){
         int tem=end;
         flag=1;
         set[i]=1;
         for(int k=1;k<=a+3-end;j++,k++){aim[j]=map[i][j-a+1];};
         end=a+3;
         dfs(a+1);
         end=tem;
         set[i]=0;
       }
     }
   }
   if(!flag){
       if(end==a){
         for(i=0;i<4;i++){
           aim[a+1]=dir[i];
           dfs(a+1);
         }
       }
       else dfs(a+1);
   }
}

int main(){
  char list[5];
  int ncase,i,j;
  cin>>ncase;
  while(ncase--){
    cin>>n;
    MIN=1000;
    memset(set,0,sizeof(set));
    for(i=1;i<=n;i++){
      cin>>list;
      for(j=0;j<4;j++){
        map[i][j+1]=list[j];
      }
    }
    for(i=0;i<4;i++){
      end=1;
      aim[1]=dir[i];
      dfs(1);
    }
    cout<<MIN<<endl;
  }
}

人家的代码

注意：

只能首尾合并相连  像 ACTG 和 CT 是不可以的

思路：

求出所以成对字符串合并会增加多少长度 并记录在表中

然后Dfs搜索就可以啦 剪枝效果更好

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<algorithm>
#include<set>
 
using namespace std;
 
const int N=11;
char s[N][N*2];
int l[N];
int addl[N][N];
bool had[N];
int ans, n;
void Findaddl(int I,int J)
{
    int w,i,j;
    for(w=max(0,l[I]-l[J]);w<l[I];++w)
    {
 
       for(i=w,j=0;j<l[J]&&i<l[I];++j,++i)
       {
           if(s[I][i]!=s[J][j])
           break;
       }
       if(j==l[J]||i==l[I])
       break;
    }
    if(j==l[J])
    addl[I][J]=0;
    else
    addl[I][J]=w+l[J]-l[I];
}
void Dfs(int sum,int Len,int pre)
{
    for(int i=0;i<n;++i)
    {
        if(!had[i])
        {
            had[i]=true;
            if(sum==n)
            {
                ans=min(ans,Len+addl[pre][i]);//枚举最小 答案
            }
            else if(Len+addl[pre][i]<ans)//剪枝
            {
                Dfs(sum+1,Len+addl[pre][i],i);
            }
            had[i]=false;
        }
    }
}
int main()
{
 
   int T;
   scanf("%d",&T);
   while(T--)
   {
       scanf("%d",&n);
       getchar();
       ans=0;
       for(int i=0;i<n;++i)
       {
           gets(s[i]);
           l[i]=strlen(s[i]);//求长度
           ans+=l[i];//记录长度和 这个和是最大长度可能
       }
       for(int i=0;i<n;++i)
       {
           for(int j=0;j<n;++j)
           {
               if(i!=j)
               Findaddl(i,j);//求i 和 j 首尾合并增加多少长度
           }
       }
       memset(had,false,sizeof(had));
       for(int i=0;i<n;++i)
       {
           had[i]=true;
           Dfs(2,l[i],i);//深搜
           had[i]=false;
       }
       printf("%d
",ans);
   }
   return 0;
}