CF178F3

沉石鱼惊旋 · 2024-02-28 15:50:22 · 题解

题目翻译

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

题目思路

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

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

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

时间复杂度 \mathcal O(n^2)。

完整代码

#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;
}