T2 额外做法_牛客博客

T2 额外做法

观察到n的范围很小。可以考虑使用 $O(n^2)$ 或 $O(n^2logn)$ 的时间复杂度解决本题。

由于答案和字典序有关，考虑使用 Trie 树。将原串的所有后缀插入到 Trie 树内，并在每个节点维护一个存放二元组的 vector。每个二原组表 $(l, r)$ 示从 Trie 树的根节点到该节点的字符串和原串的 [l, r] 相等。

然后再进行一次dfs，过程中优先走字典序小的字母，并维护一个 dfn 表示当前的字典序大小。每走到一个新节点，先 dfn++，然后将 dfn 和 vector 中的所有二元组组成一个三元组 $(dfn, l, r)$ 插入到一个新的数组 a 内部。dfs 结束后按照第一关键字排序，即可在 $O(n^2logn)$ 的时间复杂度下获得所有子串的字典序大小。

随后维护 $dp_{i}$ 表示 [1, i] 的最优答案。按照 a 从左到右遍历三元组并从 $dp_{l-1}$ 转移到 $dp_{r}$ 即可。复杂度 $O(n^2)$ 。

最终复杂度： $O(n^2logn + n^2) = O(n^2logn)$ 。如果选择桶排可以做到 $O(n^2)$ 。