2726820_ac_187ms_172k.cc

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

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

using namespace std;

int check(char a[],char b[])
{
	int i, l, r;

	l = strlen(a);
	r = strlen(b);
	for (i = 0; a[i] != '\0'; i++)
	{
		if (r>=l-i&&strncmp(&a[i],b,l-i)==0)
			return l-i;
	}
	return 0;
}

int main()
{
	int i, t, j, n, tot;
	char dna[11][101];
	int len[11][11], a[11], tmp, ans;

	scanf("%d",&t);
	while (t--)
	{
		scanf("%d",&n);
		tot = 0;
		for (i = 0; i < n; i++)
			scanf("%s",dna[i]), tot += strlen(dna[i]);
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (i!=j)
					len[i][j] = check(dna[i],dna[j]);
				else
					len[i][j] = -1;
			}
		}
		ans = -1;
		for (i = 0; i < n; i++)
			a[i] = i;
		do 
		{
			tmp = 0;
			for (i = 1; i < n; i++)
				tmp += len[a[i-1]][a[i]];
			if (tmp > ans)
			{
				ans = tmp;
			}
		} while(next_permutation(a,a+n));
		printf("%d\n",tot-ans);
	}
	return 0;
}