2365.cpp

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

/* This Code is Submitted by wywcgs for Problem 2365 on 2006-09-23 at 01:33:17 */
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

const char ALPHABET[] = "abcdefghijklmnopqrstuvwxyz+*/?";
const int N = 30, K = 12;
const int INF = 1 << 30;

map<char, int> dict;

int main()
{
	int T, f[N], cost[N][N], best[N][K], next[N][K];
	
	for(int i = 0; i < N; i++) dict[ALPHABET[i]] = i;
	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		memset(f, 0, sizeof(f));
		int n; scanf("%d", &n);
		for(int i = 0; i < n; i++) {
			char line[N+1]; scanf("%s", line);
			for(int j = 0; line[j] != 0; j++) f[dict.find(line[j])->second]++;
		}
		memset(cost, 0, sizeof(cost));
		for(int i = 0; i < N; i++)
			for(int j = i; j < N; j++)
				if(i == j) cost[i][j] = f[i];
				else cost[i][j] = cost[i][j-1]+(j-i+1)*f[j];
		for(int i = 0; i < N; i++) best[i][0] = cost[i][N-1];
		for(int i = 1; i < K; i++)
			for(int j = N-1; j >= 0; j--) {
				best[j][i] = INF;
				for(int k = j; k < N; k++)
					if(best[j][i] > best[k+1][i-1]+cost[j][k]) 
						{ best[j][i] = best[k+1][i-1]+cost[j][k]; next[j][i] = k+1; }
			}
		for(int i = K-1, j = next[0][i]; i > 0; i--, j = next[j][i]) putchar(ALPHABET[j]);
		putchar('\n');
	}
	
	return 0;
}