pku3192 DNA Assembly (暴力)

题目:

题目意思和上一篇的1699差不多，但有点细微区别，如给定以下三个串"AGCT","CT","GCTA",在本题应该输出的是5，而1699则会输出8。。由于本题的数据规模比1699还要小，串的数目和长度都不超过7，因此就暴力枚举了，最大也就达到O(7!),不会超时。生成各个串的排列时，用STL中的生成排列的函数next_permutation(),很是方便。

my code:

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int comlen(char a[],char b[])//这个函数直接复制1699的。。
{
    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 cat(char *a,char *b)
{
    int la,lb,com,i,j;
    la=strlen(a);lb=strlen(b);
    com=comlen(a,b);
    for(i=la,j=lb-com;i<la+com;i++,j++)
        a[i]=b[j];
    a[i]='\0';
}
int main()
{
    vector<int> arr;
    char str[8][8],ans[50];
    int n,i,j,tmin;
    while(cin>>n)
    {
        tmin=100000;
        for(i=0;i<n;i++) {cin>>str[i];arr.push_back(i);}
        while(next_permutation(arr.begin(),arr.end()))//生成序列
        {
            ans[0]='\0';
            for(i=0;i<n;i++)
                cat(ans,str[arr[i]]);//对每种序列进行串合并

            j=strlen(ans);//求出合并后的长度
            if(tmin>j) tmin=j;//记录最小值
        }
        cout<<tmin<<endl;
    }
    return 0;
}


PS:发觉最近做的题有点水，难点的就不会，容易点的都是枚举或暴搜。。。