2019.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2019 on 2006-07-23 at 15:27:31 */ 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

const int MAX = 2560;

class Book {
public:
	char name[32], zip[32];
	int zipl, n, best, emo, prev[10];
	void make();
	bool operator <(const Book&) const;
	bool next(const Book&) const;
};
void Book::make() {
	scanf("%d", &emo); getchar();
	best = emo; n = 0; prev[0] = -1;
	gets(name);
	int l;
	for(zipl = l = 0; true; l++) {
		while(!isalpha(name[l]) && name[l] != 0) l++;
		if(name[l] == 0) break;
		zip[zipl++] = (isupper(name[l]) ? name[l] : name[l]+'A'-'a');
	}
}
bool Book::operator <(const Book& b) const {
	return strcmp(name, b.name) < 0;
}
bool Book::next(const Book& b) const {
	int i, lmt = min(zipl, b.zipl);
	for(i = 0; i < lmt; i++)
		if(zip[i] == b.zip[i]) return false;
	return true;
}

int adj[MAX][MAX], an[MAX];

int main()
{
	Book book[MAX];
	bool change[10][MAX];
	int n, i, j, k, order[16];

	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) book[i].make(), an[i] = 0;
		sort(book, book+n);
		for(i = 0; i < n; i++)
			for(j = i+1; j < n; j++)
				if(book[i].next(book[j])) adj[i][an[i]++] = j;
		memset(change, false, sizeof(change)); memset(change[0], true, sizeof(change[0]));
		for(i = 1; i < 10; i++)
			for(j = n-1; j >= 0; j--)
				for(k = 0; change[i-1][j] && k < an[j]; k++) {
					int it = adj[j][k];
					if(book[it].best < book[it].emo+book[j].best) {
						book[it].best = book[it].emo + book[j].best;
						book[it].n = i; book[it].prev[i] = j; change[i][it] = true;
					}
				}
		int bo = 0;
		for(i = 1; i < n; i++)
			if(book[bo].best < book[i].best) bo = i;
		int m = book[bo].n;
		printf("%d\n%d\n", m+1, book[bo].best);
		for(i = m; i >= 0; i--) order[i] = bo, bo = book[bo].prev[i];
		for(i = 0; i <= m; i++) printf("%s\n", book[order[i]].name);
	}
	
	return 0;
}