Словесная игра
http://acm.pku.edu.cn/JudgeOnline/problem?id=1171

http://acm.pku.edu.cn/JudgeOnline/images/1171_1.jpg

   Словесные игры популярны дома и на телевидении. В нашем формате игры каждая буква имеет цену, и вы должны из букв составить одно или более слов, дающих максимальную суммарную стоимость. До тех пор, пока возможно,  вы подбираете все известные вам слова, иногда проверяя правописание и вычисляя их стоимость. Очевидно, это лучше сделать с помощью компьютера.

   Даны цены букв (рисунок выше), список английских слов и набор букв. Найдите в словаре слова или пары слов с наибольшей суммарной стоимостью, которые можно составить из заданного набора букв.

   Входные данные

   В первой строке находится перечисление допустимых маленьких английских букв. В последующих строках задается словарь - по одному слову в строке. Окончание ввода - символ "." (точка) в последней строке.

   Выходные данные

   В единственной строке вывести одно число - искомую наибольшую суммарную стоимость.

   Пример входных данных

prmgroa
profile
program
prom
rag
ram
rom
.
   
   Примечание

   Рекомендуется использовать при использования языка С для считывания оператор scanf в связи с большими входными данными.
   
   Пример выходных данных

24

   Анализ условия и разбор идеи решения

   Пример решения на С++:

Код:
#include <iostream>
#include <algorithm>
using namespace std;

void JooPoo()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
}

int Map[26]={2,5,4,4,1,6,5,5,1,7,6,3,5,2,3,5,7,2,1,2,4,6,6,7,5,7};
int score[40000],dict_use[26]={0},word_use[26],tmp_use[26];
char dict[8],word[40000][8];

int main()
{
	JooPoo();

	int i,j,k,n;
	gets(dict);
	for (i=0; dict[i]!='\0'; i++)
dict_use[dict[i]-'a']++;
	
	n = 0;
	while (gets(word[n]))
	{
if (word[n][0] == '.') break;
bool isword=true;
score[n]=0;
memset(word_use, 0 ,sizeof(word_use));
for (i=0; word[n][i]!='\0'; i++)
{
	if (dict_use[word[n][i]-'a'] == 0 || word_use[word[n][i]-'a'] >= dict_use[word[n][i]-'a'])
	{
isword = false;
score[n] = 0;
break;
	}
	else
word_use[word[n][i]-'a']++;
	score[n] += Map[word[n][i]-'a'];
}
if (isword == true)
	n++;
	}
	
	int Max = *max_element(&score[0], &score[n]);
	for (i=0; i<n; i++)
	{
memcpy(word_use,dict_use,sizeof(dict_use));
for (j=0; word[i][j]!='\0'; j++)
	word_use[word[i][j]-'a']--;
for (j=i+1; j<n; j++)
{
	bool isOK = true;
	memcpy(tmp_use,word_use,sizeof(word_use));
	for (k=0; word[j][k]!='\0'; k++)
	{	
tmp_use[word[j][k]-'a']--;
if (tmp_use[word[j][k]-'a'] < 0)
{
	isOK = false;
	break;
}
	}
	if (isOK == true)
	{
if (score[i] + score[j] > Max)
	Max = score[i] + score[j];
	}
}
	}

	printf("%d\n",Max);
}