pku2817.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int N;
char s[10][11];
int v[10][10];
int p[10];

int get_common(char *a, char *b)
{
	int i;
	int cnt = 0;
	i = 0;
	while (a[i]&&b[i])
	{
		if (a[i] == b[i]) cnt++;
		i++;
	}
	return cnt;
}

int get_max_length(char a[], char b[])
{
	int ans, tmp;
	int i;
	ans = 0;
	for (i = 0; i < strlen(a); i++)
	{
		tmp = get_common(a+i, b);
		if (tmp > ans) ans = tmp;
	}
	for (i = 0; i < strlen(b); i++)
	{
		tmp = get_common(a, b+i);
		if (tmp > ans) ans = tmp;
	}
	return ans;
}

void Solve()
{
	int i, j;
	int max, tmp;
	for (i = 0; i < N; i++)
		scanf("%s", s[i]);
	for (i = 0; i < N; i++)
		for (j = i + 1; j < N; j++)
			v[i][j] = v[j][i] = get_max_length(s[i], s[j]);
	for (i = 0; i < N; i++)
		p[i] = i;
	max = 0;
	do
	{
		tmp = 0;
		for (i = 0; i < N - 1; i++)
			tmp += v[p[i]][p[i + 1]];
		if (tmp > max)
			max = tmp;
	}while (next_permutation(p, p + N));
	printf("%d\n", max);
}

int main()
{
	while (EOF != scanf("%d", &N) && N)
		Solve();
	return 0;
}