1992281_ac_279ms_28k.cpp

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>

using namespace std;

int n, min;
char tmp[100];
struct node
{
	char dna[10];
}DNA[7];

int cmp(struct node a,struct node b)
{       
	return strcmp(a.dna,b.dna)>0;
}

void check(char Dna[])
{
	int k;
	bool mark;
	int leni, lenj;

	mark = 1;
	leni = strlen(tmp);
	for(k = 0; tmp[k]!='\0'; k++)
	{
		lenj = strlen(&tmp[k]);
		if(lenj<=leni)
			if(strncmp(&tmp[k],Dna,lenj)==0)
			{
				mark = 0;
				break;
			}
	}
	strcat(tmp,&Dna[lenj-mark]);
}

void input()
{	
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%s",DNA[i].dna);
	sort(DNA,DNA+n,cmp);
	min = 100;
	do
	{
		strcpy(tmp,DNA[0].dna);
		for(i = 1; i < n; i++)
			check(DNA[i].dna);
		if(strlen(tmp)<min)
			min = strlen(tmp);
	}
	while(next_permutation(DNA,DNA+n,cmp));
	printf("%d",min);
}

int main()
{
	input();
	return 1;
}