![](http://www.cppblog.com/images/cppblog_com/xiongnanbin/Lgame.gif)
在家里用电视机做字母游戏是很流行的,其中一种玩法是:每一个字母有一个数值与之对应.你收集字母组成一个或多个字以得到尽可能高的得分.除非你已有了 “找字的方法”(“a way with words”),你会把你知道的字都试一遍.有时你也许会查阅其拼写,然后计算得分。显然可以用计算机更为准确地完成此任务。上图示出了英文字母及其所对应的值,当给出英文字(word) 的表列及收集的字母时,请找出所能形成的得分最高的字或字对(pairs of words)。
格式
PROGRAM NAME: lgame
INPUT FORMAT:(file lgame.in)
输入文件lgame.in中有一行由小写字母(`a'到`z')组成的字符串, 这就是收集到字母(就是可以使用的字母),字符串由至少3个字母至多7个字母(以任意顺序) 组成。
(file lgame.dict)
词典文件lgame.dict由至多40,000行组成,文件的最后一行有'.' 表示文件的结束。其它各行每一行都是由至少3个小写字母,至多7 个小写字母组成的字符串。文件中的词已按字典顺序排序。
OUTPUT FORMAT:(file lgame.out)
在文件lgame.out的第一行,你的程序应写上最高得分(子任务A).使用上面图形中给出的字母-值对应表。
随后的每一行是由文件lgame.dict中查到的具有这个得分的所有的词和或词对(word pairs)(子任务B)。要利用图中给定的字母的值。
当两个词能够形成 一个组合(具有给定的字母)时,这两个词应该打印到同一行,两个词中间用一个空格隔开。不许重复表示词对,例如'rag prom'和'prom rag'是同样的词对,只输出字典顺序较小的那个。
输出要按照字典顺序排序,如果两个词对第一个单词的顺序相同,则按照第二个单词。
SAMPLE INPUT(file lgame.in)
prmgroa
SAMPLE INPUT(file lgame.dict)
profile
program
prom
rag
ram
rom
.
SAMPLE OUTPUT
24
program
prom rag
【参考程序】:
/*
ID: XIONGNA1
PROG: lgame
LANG: C++
*/
#include<fstream>
#include<cstring>
using namespace std;
int val[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 num[26],temp[26];
string str,data[40001];
int n,ans,sum;
void check(int n1,int n2)
{
memset(temp,0,sizeof(temp));
for (int i=0;i<data[n1].length();i++)
temp[data[n1][i]-'a']++;
for (int i=0;i<data[n2].length();i++)
temp[data[n2][i]-'a']++;
sum=0;
for (int i=0;i<26;i++)
if (temp[i]>num[i]) return ;
for (int i=0;i<26;i++)
sum+=temp[i]*val[i];
}
int main()
{
ifstream cin1("lgame.in");
ifstream cin2("lgame.dict");
ofstream cout("lgame.out");
memset(num,0,sizeof(num));
cin1>>str;
for (int i=0;i<str.length();i++) num[str[i]-'a']++;
n=0; bool bk;
while (cin2>>str,str!=".")
{
memset(temp,0,sizeof(temp));
for (int i=0;i<str.length();i++) temp[str[i]-'a']++;
bk=true;
for (int i=0;i<26;i++)
if (temp[i]>num[i])
{
bk=false; break;
}
if (bk) data[++n]=str;
}
data[++n]="";
//cout<<n<<endl;
ans=0;
for (int i=1;i<=n-1;i++)
for (int j=i+1;j<=n;j++)
{
check(i,j);
if (sum>ans) ans=sum;
}
cout<<ans<<endl;
for (int i=1;i<=n-1;i++)
for (int j=i+1;j<=n;j++)
{
check(i,j);
if (sum==ans)
{
cout<<data[i];
if (data[j]!="") cout<<' '<<data[j];
cout<<endl;
}
}
return 0;
}