2188.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2188 on 2006-03-27 at 11:12:23 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 10;
const int L = 16;
const int S_MAX = 1 << N;

int score(const char*, const char*);

int main()
{
	int n, best[N][S_MAX], scr[N][N];
	int i, j, k;
	char word[N][L];

	while(scanf("%d", &n) != EOF && n != 0) {
		memset(scr, -1, sizeof(scr)); memset(best, 0, sizeof(best));
		for(i = 0; i < n; i++) scanf("%s", word[i]);
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				scr[i][j] = scr[j][i] = max(scr[i][j], score(word[i], word[j]));
		int status = 1 << n;
		for(i = 0; i < status; i++)
			for(j = 0; j < n; j++)
				if((i & (1<<j)) && i != (1<<j)) {
					int ps = i ^ (1 << j);
					for(k = 0; k < n; k++)
						if(ps & (1<<k)) best[j][i] = max(best[j][i], best[k][ps]+scr[j][k]);
				}
		int pos = 0;
		for(i = 0; i < n; i++) pos = max(pos, best[i][status-1]);
		printf("%d\n", pos);
	}
	
	return 0;
}

int score(const char* s1, const char* s2)
{
	int len = strlen(s1), b = 0, i, j;
	
	for(i = 0; i < len; i++) {
		int n = 0;
		for(j = i; s1[j] != 0 && s2[j-i] != 0; j++)
			if(s1[j] == s2[j-i]) n++;
		b = max(n, b);
	}
	
	return b;
}