题解：CF178F1 Representative Sampling

为什么题解区全部都是可以过 F2，F3 的做法啊？这里来一个只能过 F1 的做法。

我们提前把字符串两两之间的

\operatorname{lcp}

求出来，然后直接暴力枚举子集。注意枚举时如果不是

k

元子集直接跳过。

时间复杂度：

O(C_{n}^k k^2)

。可以通过本题。

CPP

void sol(){
	int n,k;
	cin>>n>>k;
	for (int i=1;i<=n;i++) cin>>s[i];
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (i==j) continue;
			if (i>j){
				a[i][j]=a[j][i];
				continue;
			}
			int now=0;
			while (s[i][now]==s[j][now]&&now<min(sz(s[i]),sz(s[j]))) now++;
			a[i][j]=now;//lcp
		}
	}
	int ans=0;
	for (int i=0;i<(1<<n);i++){
		if (__builtin_popcount(i)!=k) continue;
		vector<int> v;
		for (int j=0;j<n;j++){
			if ((i>>j)&1) v.pb(j+1);
		}
		int sum=0;
		for (int j=0;j<k-1;j++){
			for (int l=j+1;l<k;l++){
				sum+=a[v[j]][v[l]];
			}
		}
		ans=max(ans,sum);
	}
	cout<<ans<<endl;
}

题解：CF178F1 Representative Sampling

文章操作

相关推荐

评论

题解：CF178F1 Representative Sampling