Problem 1770 --Representative Sampling (30_points)

1770: Representative Sampling (30_points)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $7$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
来自ABBYY的小明有一个与“细胞与遗传学研究所”的合作。最近,研究所用一个新的题目考验小明。题目如下。
有由n个细胞组成的一个集合(不一定不同)每个细胞是一个由小写拉丁字母组成的字符串。科学家给小明提出的问题是从给定集合中选出一个大小为k的子集,使得所选子集的代表值最大。
小明做了些研究并得出了一个结论,即一个蛋白质集合的代表制可以用一个方便计算的整数来表示。我们假设当前的集合为{a1, ..., ak},包含了k个用以表示蛋白质的字符串。那么蛋白质集合的代表值可以用如下的式子来表示:
其中f(x, y)表示字符串x和y的最长公共前缀的长度,例如:
f(" abc" ,  " abd" ) = 2  ,  f(" ab" ,  " bcd" ) = 0.
因此,蛋白质集合{" abc" ,  " abd" ,  " abe" }的代表值等于6,集合{" aaa" ,  " ba" ,  " ba" }的代表值等于2。
在发现了这个之后,小明要求赛事参与者写一个程序选出,给定蛋白质的集合中的大小为k的子集中,能获得最大可能代表性值得一个子集。帮助他解决这个问题吧!

输入数据第一行包含2个正整数n和k(1≤k≤n),由一个空格隔开。接下来的n行每一行都包含对蛋白质的描述。每个蛋白质都是一个仅有不超过500个小写拉丁字母组成的非空字符串。有些字符串可能是相等的。 

输出一个整数,表示给定蛋白质集合的大小为k的子集的代表值最大可能是多少。 

3 2
aba
bzd
abq
2

【样例输入2】 

4  3 
eee 
rrr 
ttt 
qqq 
【样例输出2】 

【样例输入3】 
4  3 
aaa 
abba 
abbc 
abbd 
【样例输出3】 

20%的数据保证:1 ≤ n ≤ 20 

50%的数据保证:1 ≤ n ≤ 100 
100%的数据保证:1 ≤ n ≤ 2000 

推荐代码 查看1770 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 sqrjy 606426 2020-07-09 21:00:24

赛题来源/所属竞赛 蓝桥杯 挑战算法之蓝桥杯

竞赛编号 竞赛名称 竞赛时间 访问比赛