题目大意：

　　给你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，然后就把它废弃掉。

　　这就相当于动态开数组。

　　这样就同时解决了时间和空间上的问题。

1 #include
     
       2 #include
      
        3 #include
       
         4 const int inf=0x7fffffff; 5 const int N=2000,K=2001; 6 std::string s[N]; 7 int n,k,lcp[N]; 8 int f[N<<1][K],cnt; 9 void dp(const int &l,const int &r,const int &id) {10     if(l==r) return;11     int mid=0;12     for(register int i=l+1;i<=r;i++) {13         if(lcp[i]
        
         mid-l) break;21         for(register int j=0;j<=k;j++) {22             if(j>r-mid+1) break;23             if(i+j<=k) f[id][i+j]=std::max(f[id][i+j],f[lid][i]+f[rid][j]+lcp[mid]*i*j);24         }25     }26     cnt-=2;27 }28 int main() {29     std::ios_base::sync_with_stdio(false);30     std::cin.tie(NULL);31     std::cin>>n>>k;32     for(register int i=0;i
         
          >s[i];34     }35     std::sort(&s[0],&s[n]);36     lcp[0]=inf;37     for(register int i=1;i