1992243_wa.cpp

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

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

using namespace std;

int n, max, sum;
int cost[7][8];
struct node
{
	int no;
	char dna[10];
}DNA[7];

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

void check(int j, int i)
{
	int k;
	int leni, lenj;

	cost[j][i] = 0;
	leni = strlen(DNA[i].dna);
	for(k = 0; DNA[j].dna[k]!='\0'; k++)
	{
		lenj = strlen(&DNA[j].dna[k]);
		if(lenj<=leni)
			if(strncmp(&DNA[j].dna[k],DNA[i].dna,lenj)==0)
			{
				cost[j][i] = lenj;
				break;
			}
	}
	cost[i][j] = 0;
	lenj = strlen(DNA[j].dna);
	for(k = 0; DNA[i].dna[k]!='\0'; k++)
	{
		leni = strlen(&DNA[i].dna[k]);
		if(leni<=lenj)
			if(strncmp(&DNA[i].dna[k],DNA[j].dna,leni)==0)
			{
				cost[i][j] = leni;
				break;
			}
	}
}

void input()
{
	int i, j, total;

	scanf("%d",&n);
	total = 0;
	for(i = 0; i < n; i++)
	{
		scanf("%s",DNA[i].dna);
		total += strlen(DNA[i].dna);
		DNA[i].no = i;
		for(j = i-1; j >= 0; j--)
			check(j,i);
	}
	sort(DNA,DNA+n,cmp);
	max = 0;
	do
	{
		sum = 0;
		for(i = 0; i < n-1; i++)
			sum += cost[DNA[i].no][DNA[i+1].no];
		if(sum > max)
			max = sum;
	}
	while(next_permutation(DNA,DNA+n,cmp));
	printf("%d",total-max);
}

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