2241.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2241 on 2006-05-22 at 18:19:06 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

const int LN = 26;

vector<int> v[LN];
int ind[LN], best;

class Trie {
public:
	int f, w;
	Trie *child[LN];
	Trie(int);
	void insert(const char*);
	void find(int) const;
};
Trie::Trie(int fl) : f(fl), w(0) {
	int i;
	for(i = 0; i < LN; i++) child[i] = NULL;
}
void Trie::insert(const char* str) {
	if(str[f] == 0) { w = 1; return; }
	int o = str[f] - 'a';
	if(child[o] == NULL) child[o] = new Trie(f+1);
	child[o]->insert(str);
}
void Trie::find(int s) const {
	int i;
	if(w) best = max(s, best);
	for(i = 0; i < LN; i++) {
		if(child[i] == NULL || ind[i] == (int)v[i].size()) continue;
		ind[i]++; child[i]->find(s+v[i][ind[i]-1]); ind[i]--;
	}
}

int main()
{
	Trie *root = new Trie(0);
	int n, T, t, i;
	char word[LN];

	scanf("%d\n", &n);
	for(i = 0; i < n; i++) root->insert(gets(word));
	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		for(i = 0; i < LN; i++) v[i].clear();
		memset(ind, 0, sizeof(ind)); best = 0;
		int m; scanf("%d", &m);
		for(i = 0; i < m; i++) {
			char c; int s; scanf("\n%c %d", &c, &s);
			v[c-'a'].push_back(s);
		}
		for(i = 0; i < LN; i++) sort(v[i].begin(), v[i].end(), greater<int>());
		root->find(0); printf("%d\n", best);
	}
	
	return 0;
}