为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/lgame
来自NOCOW
< USACO
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 4 .3中的OI题目Letter Game的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
[编辑] 问题分析
这个题要仔细读，理解题意。起初我理解得不对，以为是输出的每个结果都必须是输入的一个排列，不能多也不能少。这种理解不正确。汗，我一直以为样例居然是错的，其实使用的字典不一样。
这道题正确的理解应该是，在结果的单词或词组构所成的字母中，每个字母出现的频数不大于输入的字符串中每个字母的频数。也就是例如输入是 aaa，字典中有单词 a,aa,aaa,aaaa，其中a,aa,aaa都是符合条件的解，但只有aaa才是要输出的最优解。
理解题意以后编程不难，直接枚举每种可行解，单词可以在O(n)内解决，词组要O(N^2)。但是对于40000个单词还是太多了。可以发现，大多数单词都是用不到的，而所以我们可以在读入字典的时候直接去除非可行解的单词，即该单词有输入字串中未出现的字母，或者在该单词中的字母中，有频数大于输入字串所含该字母频数的（例：输入字串为aabb，该单词为aaa，其中a的频数大于输入字串，必定无法有输入字串构成）。
这样优化可以去掉绝大部分的冗余，使得程序能够在很快的时间内算出结果。
所后别忘了对结果排序，可以把单词当作一个第二个单词为空串的词组，按字典顺序排序即可。
- 枚举字典方向略有问题吧。注意到输入的长度只有3-7个字符，枚举所有排列，在每个排列里取所有前缀，对每一个前缀取所有分割，才不到7! * 7 * 7种，一共也就二十万吧。。。
[编辑] 注意
题目中提到"find the highest scoring words or pairs of words that can be formed." 就是说,让你找到最高的得分,在第一行输出 然后下面要输出所有的得分最高的单词或词组,并且按照字典序输出.
额，给出的单词长度在3~7之间，所以最多只能用两个单词。。
