题目大意:
给你n个字符串,要求从中选出k个字符串,使得字符串两两lcp之和最大。
思路:
动态规划。
首先将所有的字符串排序,求出相邻两个字符串的lcp长度(很显然,对于某一个字符串,和它lcp最长的字符串一定是和它字典序最接近的一个)。
接下来考虑一种类似于分治的做法。
首先找出当前区间内最小的lcp。
很显然,在这个lcp左边的字符串和右边的字符串配对时的lcp一定是这个lcp。
假如我们在左边取了i个,右边取了j个,这个lcp对答案的贡献是lcp*i*j。
接下来递归处理左半边的区间和右半边的区间即可。
考虑如何表示状态。
不难想到用f[l][r][k]表示在l~r之间取k个字符串。
每次递归枚举左右区间取的个数。
总共有n^2k种状态,如果使用记忆化,很显然数组开不下。
不使用记忆化则会TLE。
接下来考虑改进这个状态。
我们递归的时候不需要针对某一个具体的k,而是在l,r这个状态内枚举k。
显然,对于同一个l,r,k,只会被转移一次。
而同一组l,r只会被转移一次。
因此我们只需要在递归的时候存一下l,r,然后就把它废弃掉。
这就相当于动态开数组。
这样就同时解决了时间和空间上的问题。
#include<string>
#include<iostream>
#include<algorithm>
const int inf=0x7fffffff;
const int N=,K=;
std::string s[N];
int n,k,lcp[N];
int f[N<<][K],cnt;
void dp(const int &l,const int &r,const int &id) {
if(l==r) return;
int mid=;
for(register int i=l+;i<=r;i++) {
if(lcp[i]<lcp[mid]) mid=i;
}
const int lid=cnt++,rid=cnt++;
dp(l,mid-,lid);
dp(mid,r,rid);
__builtin_memset(f[id],,sizeof f[id]);
for(register int i=;i<=k;i++) {
if(i>mid-l) break;
for(register int j=;j<=k;j++) {
if(j>r-mid+) break;
if(i+j<=k) f[id][i+j]=std::max(f[id][i+j],f[lid][i]+f[rid][j]+lcp[mid]*i*j);
}
}
cnt-=;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin>>n>>k;
for(register int i=;i<n;i++) {
std::cin>>s[i];
}
std::sort(&s[],&s[n]);
lcp[]=inf;
for(register int i=;i<n;i++) {
lcp[i]=std::min(s[i].length(),s[i-].length());
for(register int j=;j<lcp[i];j++) {
if(s[i][j]!=s[i-][j]) {
lcp[i]=j;
}
}
}
dp(,n-,cnt++);
std::cout<<f[][k]<<std::endl;
return ;
}