【算法】Representative Sampling (30_points)

算法训练 Representative Sampling (30_points)

时间限制：2.0s 内存限制：256.0MB

【题目描述】
来自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的子集的代表值最大可能是多少。

【数据规模】
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

这个题比较有意思，做了不少时间。用的是全排列，穷举，结果只得了10分。都是超时，测试数据太大了。

代码：

import java.util.Scanner;

public class Main {
	
	static int k,max;
	public static void main(String[] args) {
		
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			String ss=sc.nextLine();
			String[] ch=ss.split(" ");
			int n=Integer.parseInt(ch[0]);
			k=Integer.parseInt(ch[1]);
			String[] data=new String[n];
			for (int i = 0; i < data.length; i++) {
				data[i]=sc.nextLine();
			}
			f(data,0);
			System.out.println(max);
		}
	}

	private static void f(String[] data, int w) {
		
		if(k==w){
			getK(data);
		}
		
		for (int j = w; j < data.length; j++) {
			{String t=data[w];data[w]=data[j];data[j]=t;}//试探
			f(data,w+1);
			{String t=data[w];data[w]=data[j];data[j]=t;}//回溯
		}
	}

	private static void getK(String[] data) {
		int sum=0;
		for (int i = 0; i < k; i++) {
			for (int j = i+1; j < k; j++) {
				int count=0;
				for (int t = 0; t < data[i].length()&&t < data[j].length(); t++) {
					if(data[i].charAt(t)!=data[j].charAt(t))
						break;
					count++;
				}
				sum+=count;
			}
		}
		if(sum>max)
			max=sum;
	}
}