2376.cpp

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

/* This Code is Submitted by wywcgs for Problem 2376 on 2006-09-26 at 15:02:34 */
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int N = 51200;
const int L = 48;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const
		{ return strcmp(s1, s2) < 0; }
};

double f, best[L*L];
int prev[L*L];
char word[N][L], line[L*L], w[L*L];
map<char*, double, cmp> dict;

int main()
{
	scanf("%lf", &f); dict.clear();
	do gets(line);
	while (strcmp(line,"DICT BEGIN"));
	for(int wn = 0; true; wn++) {
		gets(line);
		if(!strcmp(line, "DICT END")) break;
		double wf;
		sscanf(line, "%s %lf", word[wn], &wf);
		dict[word[wn]] = wf/f;
	}
	do gets(line);
	while (strcmp(line,"SENT BEGIN"));
	while(true) {
		gets(line);
		if(!strcmp(line, "SENT END")) break;
		best[0] = 1; prev[0] = -1;
		int len = strlen(line), tail = len/4*4;
		for(int i = 4; i != tail+4; i += 4) {
			best[i] = 0;
			for(int j = 0; j < i; j += 4) {
				for(int k = j; k < i; k++) w[k-j] = line[k];
				w[i-j] = 0;
				double r = best[j];
				if(dict.count(w)) r *= dict.find(w)->second;
				else if(i-j == 4) r /= f;
				else continue;
				if(best[i] < r) { best[i] = r; prev[i] = j; }
			}
		}
		int stack[L*L], top = 0;
		for(int i = tail; i >= 0; i = prev[i]) stack[top++] = i;
		for(int i = top-1; i > 0; i--) {
			for(int j = stack[i]; j < stack[i-1]; j++) putchar(line[j]);
			putchar(i == 1 ? '\n' : ' ');
		}
	}
	
	return 0;
}