题解 AT3974 【[AGC026E] Synchronized Subsequence】

· · 题解

令 a_i 表示第 i 个 \mathtt{a} 的位置，b_i 表示第 i 个 \mathtt{b} 的位置。

考虑如何比较两个字符串的字典序，可以发现当某个前缀相同时应该比较后缀，所以考虑从后往前 DP：

令 dp(i) 表示只考虑所有的 a_{i \sim N} 和 b_{i \sim N}，也就是第 i 对以及之后的 \mathtt{a}, \mathtt{b} 的情况下的字典序最大的串。

注意不是第 i 对 \mathtt{a}, \mathtt{b} 以及它们之后的所有字符都一定选择，而是一对一对的选择的。

那么答案就为 dp(1)。而 dp(i) 可以从两个方向转移，也就是 a_i 和 b_i 保留或者删掉。

如果删掉，就直接从 dp(i + 1) 转移而来。

否则考虑如果保留第 i 对 \mathtt{a}, \mathtt{b} 的话会怎么样，根据先后顺序分成两类讨论：

  1. 红色的字符就是第 $i$ 对 $\mathtt{a}, \mathtt{b}$，绿色的字符表示第 $i$ 对之前的字符，蓝色的字符表示第 $i$ 对之后的字符。 注意绿色的字符只可能是 $\mathtt{b}$，而蓝色的字符只可能是 $\mathtt{a}$。因为绿色的字符不会被保留，之后忽略它们。 既然已经确定了必须选取 $a_i, b_i$，因为要让字典序尽量大，所以 $a_i$ 到 $b_i$ 之间所有的 $\mathtt{a}$ 都应该被删掉。 也就是说，$dp(i)$ 就应该等于 $\mathtt{ab} + dp(k)$，其中 $k$ 为完全在 $b_i$ 之后的第一对 $a_k, b_k$ 的编号。
  2. 红色的字符就是第 $i$ 对 $\mathtt{a}, \mathtt{b}$，绿色的字符表示第 $i$ 对之前的字符，蓝色的字符表示第 $i$ 对之后的字符。 注意绿色的字符只可能是 $\mathtt{a}$，而蓝色的字符只可能是 $\mathtt{b}$。因为绿色的字符不会被保留，之后忽略它们。 既然已经确定了必须选取 $a_i, b_i$，因为要让字典序尽量大，所以 $a_i$ 到 $b_i$ 之间所有的 $\mathtt{b}$ 都应该被保留。 而确定要保留这些 $\mathtt{b}$，又会导致往后包含了更多的 $\mathtt{b}$，同理被包含的 $\mathtt{b}$ 也应该被保留，连锁反应会一直进行下去，直到某一次不包含了更多的 $\mathtt{b}$ 为止。举个例子： 考虑 $\mathtt{{\color{blue}b}b{\color{blue}a}babbbabaaaabbabaaaabb}$， 选取 $\mathtt{{\color{red}b}{\color{blue}b}{\color{red}a}b{\color{blue}a}bbbabaaaabbabaaaabb}$， 选取 $\mathtt{{\color{red}{bba}}{\color{blue}b}{\color{red}a}bbb{\color{blue}a}baaaabbabaaaabb}$， 选取 $\mathtt{{\color{red}{bbaba}}{\color{blue}{bbb}}{\color{red}a}b{\color{blue}{aaa}}abbabaaaabb}$， 选取 $\mathtt{{\color{red}{bbababbba}}{\color{blue}b}{\color{red}{aaa}}{\color{blue}a}bbabaaaabb}$， 选取 $\mathtt{{\color{red}{bbababbbabaaaa}}bbabaaaabb}$。 在这种情况下，$dp(i) = \mathtt{bbababbbabaaaa} + dp(k)$，其中 $k$ 为后面部分的第一对 $a_k, b_k$ 的编号。

所以只要求出以上两类的结果就行，第 1 类可以预处理，第 2 类的开头的字符串，可以直接扫一遍判断。

时间复杂度为 \mathcal O (N^2)，评测链接。