题目翻译

给定 $n(n\leq 2000)$ 个串，选定 $k$ 个串，求出最大两两 LCP。

题目思路

首先把给定串按字典序排序，保证相邻 LCP 最大。

考虑 dp，$f_{l,r,x}$ 表示选择 $[l,r]$ 中有 $x$ 个串的最大两两 LCP。

类似分治，转移的时候枚举相邻 LCM 最小的点 $m$，一定是在 $m$ 断开最优。转移枚举左右段分别选几个串，加上串的个数乘上 $\operatorname{lcp}(s_m,s_{m+1})$。这个 $\operatorname{lcp}$ 需要预处理。

时间复杂度极小常数 $\mathcal O(n)$。

完整代码

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
typedef vector<int> vi;
int n, k;
int lcp[2020];
string s[2020];
vi solve(int l, int r)
{
    if (l == r)
        return vi(2, 0);
    int m = min_element(lcp + l, lcp + r) - lcp;
    vi L = solve(l, m);
    vi R = solve(m + 1, r);
    vi f(r - l + 2, 0);
    for (int l = 0; l < L.size(); l++)
        for (int r = 0; r < R.size(); r++)
            chkmx(f[l + r], L[l] + R[r] + lcp[m] * l * r);
    return f;
}
int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++)
    {
        int len = 0;
        while (len < min(s[i].size(), s[i + 1].size()) && s[i][len] == s[i + 1][len])
            len++;
        lcp[i] = len;
    }
    cout << solve(1, n)[k] << endl;
    return 0;
}