题解：P3881 [JLOI2008] CODES

· · 题解

题目传送门

这道题的正解为搜索加剪枝，简单来说就是暴搜。

我们可以用一个 dfs 函数，这个函数拥有两个参数：字符串 a 和 b，且保证前者长度大于后者。在每一次搜索中，我们遍历输入的所有字符串，如果 b 加上当前的字符串 s_i 后 a 为其前缀或其为 a 的前缀，那么就可以进行下一次搜索。

这么抽象的说明肯定不容易看懂，让我们先分析一下样例，很容易就能看懂。

样例输入：

5
0110
00
111
001100
110

先演示最优解是怎么形成的（正常不可能一次找到最优解）：

  1. 先往 dfs 函数里塞两个字符串，分别为 001100 和 00。
  2. 在所有的字符串里遍历，发现如果字符串 00 加上字符串 110 变成 00110 时，仍是 001100 的前缀。
  3. 进行下一次搜索：再次遍历，发现 00110 加上 0110 变成 001100110 后 001100 仍为其前缀。
  4. 进行下一次搜索：可以使 001100 加上 110 变成 001100110，仍为 001100110 的前缀。
  5. 发现两个字符串相等，找到最优解。

如果就这么硬生生地实现那么肯定会超时，那么我们要实现一个剪枝：如果当前字符串长度比最优解要长，那么直接结束本次搜索。

接下来就很好实现了！代码放在下面的记录里了，尽量自己写~

AC 记录（带代码）