题解：CF1003F Abbreviation

· · 题解

本做法来源于一份 chemthan 在 Codeforces 上的提交，原作者的实现是 O(n^4) 的，但是我发现可以将其优化到 O(n^2) 从而爆标。

这份代码的思路是预处理每个子区间的左边最近的不相交的相等区间。

预处理过程，则枚举子区间的左端点 x，同时将所有右端点在 x 左边的子区间加入字典树，对于每个字典树上的节点，记录其代表的区间在数组中最右边的出现位置。

然后，升序枚举当前子区间的右端点 y，通过字典树可以快速查询 [x,y] 的左边最近的出现位置。

虽然字典树单词查询一个字符串的复杂度是 O(|S|) 的，但是这里，前一个被查询的字符串是后一个被查询的字符串的前缀，所以后一个字符串从前一个字符串对应的末尾节点开始查找就可以了，所以复杂度等于最后一个字符串的长度。

完成预处理之后，采用 DP，令 f_{l,r} 为最右边的区间是 [l,r] 时的答案。

转移的话，上一个选择的区间肯定是自己左边最近的相等区间，这个已经预处理出来了。

本做法的预处理部分可以做到 O(n^2)，但是作者写成了 O(n^4)，所以我对作者的代码进行了修改。

DP 部分也可以做到 O(n^2)，所以总的时间复杂度是 O(n^2) 的。

但是，空间复杂度仍然是 O(n^3) 的，原因是最多 O(n^2) 个节点，每种节点都有 n 种可能的连边，所以字典树的 nxt 数组得开到 n^2 \times n。

但是注意到实际上只会使用 O(n^2) 的空间。

所以，如果想要降低空间复杂度的话，可以考虑开 unordered_map 或者 map 等。

如果开 map 的话，就只有 O(n^2) 的空间占用和 O(n^2 \log n) 的时间复杂度，仍然优于官方 std。

// by chemthan
#include <bits/stdc++.h>
using namespace std;

const int N = 305;                    // max number of words
const int SIG = N;                    // alphabet size (distinct words)
const int T = N * (N + 1) / 2 + 5;    // upper bound of trie nodes per build

int n, m;
int id[N], lenw[N];
string w[N];

int f[N][N], dp[N][N];               // f[i][j]: previous start of block equal to [i..j]
int nxt[T][SIG], val[T], ptr;        // trie
long long pref[N];                   // prefix sum of word lengths

unordered_map<string, int> mp;

inline int get_id(const string &s) {
    auto it = mp.find(s);
    if (it != mp.end()) return it->second;
    return mp[s] = ++m;
}
int rem[N];
inline void add(int l, int r) {
    int u = 0;
    for (int i = l; i <= r; ++i) {
        if (!nxt[u][id[i]]) nxt[u][id[i]] = ++ptr;
        u = nxt[u][id[i]];
        val[u] = max(val[u], l);
    }
    rem[l]=u;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        id[i] = get_id(w[i]);
        lenw[i] = (int)w[i].size();
        pref[i] = pref[i - 1] + lenw[i];
    }

    int total = (int)pref[n] + (n - 1);      // original length with spaces
    int ans = total;

    // prepare f with -1
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) f[i][j] = -1;
    }

    // build f: for each split point i, trie of all segments ending at i-1
    for (int i = 2; i <= n; ++i) {
        for (int l = 1; l < i - 1; ++l){
            int u=rem[l];
            if(!nxt[u][id[i-1]])nxt[u][id[i-1]]=++ptr;
            u=nxt[u][id[i-1]];
            val[u]=max(val[u],l);
            rem[l]=u;
        }
        add(i-1,i-1);
        int u = 0;
        for (int r = i; r <= n; ++r) {
            int v = nxt[u][id[r]];
            if (!v) break;
            u = v;
            f[i][r] = val[u];                 // previous start pv of a block equal to [i..r]
        }
    }

    // DP count of non-overlapping equal segments ending at [i..j]
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; ++j) {
            int pv = f[i][j];
            dp[i][j] = 1;
            if (pv != -1) dp[i][j] = dp[pv][pv + (j - i)] + 1;

            if (dp[i][j] > 1) {
                // saving per occurrence: (sum len) + spaces - initials
                // = (pref[j]-pref[i-1]) + (j-i) - (j-i+1) = (pref[j]-pref[i-1]) - 1
                int save_one = (int)(pref[j] - pref[i - 1]) - 1;
                ans = min(ans, total - save_one * dp[i][j]);
            }
        }
    }

    cout << ans << '\n';
    return 0;
}