1651.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1651 on 2006-03-01 at 14:18:21 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N_MAX = 15;
const int S_MAX = 1 << N_MAX;
const int L_MAX = 128;
const int INF = 1600;

class String {
public:
	char gene[L_MAX];
	int len, over[N_MAX];
	void make();
	bool substring(const String&) const;
	void overlap(const String&, const int);
};
void String::make() {
	scanf("%s", gene);
	len = strlen(gene);
	memset(over, 0, sizeof(over));
}
bool String::substring(const String& s) const {
	if(len < s.len) return false;
	else return strstr(gene, s.gene) != NULL;
}
void String::overlap(const String& s, const int n) {
	int minl = min(len, s.len), i;
	for(i = minl; i >= 0; i--)
		if(!strncmp(gene+len-i, s.gene, i)) break;
	over[n] = i;
}

int minlen[N_MAX][S_MAX];

int main()
{
	String word[L_MAX];
	int n, t, T, i, j, k;

	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		scanf("%d", &n);
		for(i = 0; i < n; i++) word[i].make();
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				if(i != j && word[i].substring(word[j])) word[j--] = word[--n];
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++) word[i].overlap(word[j], j);
		int status = 1 << n;
		for(i = 0; i < status; i++)
			for(j = 0; j < n; j++) {
				int &x = minlen[j][i];
				if(i == (1<<j)) x = word[j].len;
				else if((i & (1<<j)) != 0) {
					x = INF;
					int st = i ^ (1 << j);
					for(k = 0; k < n; k++)
						if(st & (1<<k))
							 x = min(x, word[j].len-word[j].over[k]+minlen[k][st]);
				}
			}
		printf("Scenario #%d:\n", t);
		int prev = -1;
		for(status = (1<<n)-1; status != 0; status ^= 1<<prev) {
			int best = -1, bl;
			char *part;
			for(i = 0; i < n; i++)
				if((status & (1 << i)) != 0) {
					char *p = word[i].gene;
					if(prev != -1) {
						minlen[i][status] -= word[prev].over[i];
						p += word[prev].over[i];
					}
					if(best == -1 || minlen[i][status] < bl || 
						(minlen[i][status] == bl && strcmp(p, part) < 0)) {
						best = i; bl = minlen[i][status]; part = p;
					}
				}
			prev = best;
			printf("%s", part);
		}
		printf("\n\n");
	}
	
	return 0;
}