题目描述

[pic][pic] [pic] 算法训练 Representative Sampling (30_points)   时间限制：2.0s   内存限制：256.0MB     【题目描述】 　　来自ABBYY的小明有一个与“细胞与遗传学研究所”的合作。最近，研究所用一个新的 题目考验小明。题目如下。 　　有由n个细胞组成的一个集合（不一定不同）每个细胞是一个由小写拉丁字母组成的 字符串。科学家给小明提出的问题是从给定集合中选出一个大小为k的子集，使得所选子 集的代表值最大。 　　小明做了些研究并得出了一个结论，即一个蛋白质集合的代表制可以用一个方便计 算的整数来表示。我们假设当前的集合为{a1, ..., ak}，包含了k个用以表示蛋白质的 字符串。那么蛋白质集合的代表值可以用如下的式子来表示： 　　其中f(x, y)表示字符串x和y的最长公共前缀的长度，例如： 　　f("abc",

输出格式

输出一个整数，表示给定蛋白质集合的大小为k的子集的代表值最大可能是多少。 【数据规模】 　　20%的数据保证：1 ≤ n ≤ 20 　　50%的数据保证：1 ≤ n ≤ 100 　　100%的数据保证：1 ≤ n ≤ 2000 【样例输入1】 　　3 2 　　aba 　　bzd 　　abq 【样例输出1】 　　2 【样例输入2】 　　4 3 　　eee 　　rrr 　　ttt 　　qqq 【样例输出2】 　　0 【样例输入3】 　　4 3 　　aaa 　　abba 　　abbc 　　abbd 【样例输出3】 　　9

来源

蓝桥杯 算法训练