CF2045H - Missing Separators 题解

CF2045H - Missing Separators

题面

您有一本字典，它是按字母顺序排列的多个单词的列表。每个单词都由大写英文字母组成。

您想打印这本字典。然而，打印系统出现了一个错误，列表中的所有单词都紧挨着打印，单词之间没有任何分隔符。现在，您最终得到的字符串 \(S\) 是字典中所有单词按照所列顺序连接而成的。

您的任务是将 \(S\) 拆分为一个或多个单词，从而重建字典。请注意，重建后的字典必须由按字母顺序排列的不同单词组成。此外，您还要最大限度地增加字典中的单词数量。如果有多部字词数最多的词典，您可以任选一部。

题解

这场比赛全是神仙题，orz。

考虑设计 \(dp\) 数组，\(dp[x][y]\) 表示将 \(S[x \ldots y]\) 分割成为一个单词的最多单词数。

可以发现 \(dp[x][y]\) 向 \(dp[y + 1][z]\) 的转移当且仅当 \(S[x \ldots y]\) 的字典序比 \(S[y + 1 \ldots z]\) 的字典序小。

唯一的问题是，这个 \(dp\) 方式是 \(O(n^3)\) 的，我们不能接受，因此我们考虑找到一个关键点 \(z\)，使得 \(S[x \ldots y]\) 的字典序比 \(S[y + 1 \ldots z]\) 的字典序小，那么 \(dp[y + 1][z + k](k \ge 0)\) 的情况可以由前者覆盖。

我们考虑这个点 \(z\) 如何寻找，可以发现我们可以求出 \(S[x \ldots y]\) 与 \(S[y + 1 \ldots]\) 的最长公共前缀，他们具有最长公共前缀的长度为 \(k\)，显而易见这个 \(k\) 即是我们所求的 \(z\)。

我们考虑如何求出 \(S[x \ldots y]\) 与 \(S[y + 1 \ldots]\) 的最长公共前缀 \(LCPS[i][j]\)，我们可以倒序枚举 \(S[i\ldots]\) 和 \(S[j\ldots]\)，如果 \(S[i] = S[j]\)，那么 \(LCPS[i][j] = LCPS[i + 1][j + 1] + 1\)，这样我们可以预处理出任意后缀的最长公共前缀了。

接下来考虑转移，对于一个位，首先可以继承前者状态 \(dp[i][j] = dp[i][j - 1]\)，往分割后的字符串后加上一个字符不改变数量。另一方面，对于具有最长公共前缀长度为 \(k\) 的两个相邻串 \(dp[x][y]\) 可以转移到 \(dp[y + 1][y + 1 + k]\)，因为 \(S[x \ldots y]\) 比 \(S[y + 1 \ldots y + 1 + k]\) 短，所以字典序一定更小。在转移中记录一下前一字符串的开头即可，方便后续输出答案。

时间复杂度 \(O(\vert S \vert^2)\)。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010;
char s[N];
int dp[N][N], LCPS[N][N];
int pre[N][N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = n; i; i -- ) {
        for (int j = n; j; j -- ) {
            if (s[i] == s[j]) LCPS[i][j] = LCPS[i + 1][j + 1] + 1;
            dp[i][j] = -1e9;
        }
    }
    dp[1][0] = 1;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = i; j <= n; j ++ ) {
            if (dp[i][j - 1] > dp[i][j]) {
                dp[i][j] = dp[i][j - 1];
                pre[i][j] = pre[i][j - 1];
            }
            if (j == n) continue;
            int k = min(j - i + 1, LCPS[i][j + 1]);
            if (j + 1 + k > n) continue;
            if (i + k > j || s[i + k] < s[j + 1 + k]) {
                if (dp[i][j] + 1 > dp[j + 1][j + 1 + k]) {
                    dp[j + 1][j + 1 + k] = dp[i][j] + 1;
                    pre[j + 1][j + 1 + k] = i;
                }
            }
        }
    }
    int cnt = 0, last = 0, ed = n;
    for (int i = 1; i <= n; i ++ )
        if (dp[i][n] > cnt)
            cnt = dp[i][n], last = i;
    vector<int> ans(1, n + 1);
    while (last) {
        int t = pre[last][ed];
        ans.push_back(last);
        ed = last - 1, last = t;
    }
    reverse(ans.begin(), ans.end());
    cout << cnt << "\n";
    for (int i = 0; i + 1 < ans.size(); i ++ , cout << "\n")
        for (int j = ans[i]; j < ans[i + 1]; j ++ )
            cout << s[j];
    return 0;
}