pku1699 Best Sequence (简单深搜)

题目:

题目大意是说给定几个串，然后求出最短公共父串的长度。。由于串的个数，以及每个串的长度都比较小，所以直接采用搜索。先保存任意两个串合并后的长度，然后搜索出所有串合并后的最短长度。具体如下：

str[i]:保存输入的串第i个串

a[i][j]:保存第j个串加到第i个串后面时，最短需要在i串后添加的长度。如str[i]="AGCT",str[j]="CTA"，则a[i][j]=1,a[j][i]=3;注意的是，如果s[j]="GC"，则a[i][j]=2,即合并后的串为"AGCTGC",而不是"AGCT"。

x[i]:保存结果中第i个串，在原始串序列中的位置。

my code:

 

 

#include<iostream>
using namespace std;
char str[11][21];
int n,a[11][11],ans,use[11],x[11];
int comlen(char a[],char b[])//求b串合并到a串后,a串需要增加的长度
{
    int la,lb,j,k,t,i;
    la=strlen(a);
    lb=strlen(b);
    for(k=la>lb?la-lb:0,j=0,t=0,i=k;i<la;)
    {
        if(a[i]!=b[j]) {t=0;j=0;k++;i=k;}
        else {i++;j++;t++;}
    }
    t=lb-t;
    return t;
}
void res(int p,int len)
{
    if(p==n+1)
    {
        if(len<ans) ans=len;
        return ;
    }
    for(x[p]=1;x[p]<=n;x[p]++)
    {
        if(len+a[x[p-1]][x[p]]>ans) continue;//加个小剪枝，快了几百MS
        if(use[x[p]]) continue;
        use[x[p]]=1;
        if(p<=n) res(p+1,len+a[x[p-1]][x[p]]);
        use[x[p]]=0;
    }
}
int main()
{
    int t,i,j;
    cin>>t;
    while(t--)
    {
        cin>>n;ans=10000;
        memset(use,0,sizeof(use));
        for(i=1;i<=n;i++)cin>>str[i];
        for(i=1;i<=n;i++)
            for(j=i+1;j<=n;j++)
            {
                a[i][j]=comlen(str[i],str[j]);
                a[j][i]=comlen(str[j],str[i]);
            }
        for(i=1;i<=n;i++) a[0][i]=strlen(str[i]);
        res(1,0);
        cout<<ans<<endl;
    }
    return 0;
}