Serval and Brain Power

题目大意

输出一个给定字符串 $S$ 的子序列的最长长度，要求这个子序列由大于 $1$ 的字符串循环出现 $k$ 次组成。

数据范围满足，$\lvert S\rvert\le 80$。

思路

因为 $S$ 很短，所以考虑使用奇奇怪怪的方法进行求解。

考虑两种暴力：

对于重复 $k$ 次的字符串，我们可以暴力枚举将 $S$ 分为 $k$ 段，时间复杂度为 $O(n^{k-1})$ 。对着这分成的 $k$ 段跑一个最长公共子序列，时间复杂度为 $O(n^k)$。所以将这两个操作结合起来，得到这个暴力程序的总时间复杂度为 $O(n^{2k-1})$。

同样的对于重复 $k$ 次的字符串，容易发现单个串的长度最长为 $\lfloor \dfrac{n}{k}\rfloor$。我们可以枚举一个长度为 $\lfloor \dfrac{n}{k}\rfloor$ 的区间的起点，然后暴力枚举这个区间中的数选货不选再与原串跑一个最多的匹配。其中枚举起点的时间复杂度为 $O(n)$，选择元素的时间复杂度为 $O(2^{\lfloor \dfrac{n}{k}\rfloor})$ ，跑最多匹配的时间复杂度为 $O(n)$，所以总共时间复杂度为 $O(n^2\cdot 2^{\lfloor \dfrac{n}{k}\rfloor})$。

考虑将两种暴力结合一下，在 $k\le 3$ 的时候使用第 $1$ 种暴力，在 $k\ge 5$ 的时候使用第 $2$ 种暴力，在 $k=4$ 的时候不处理因为这种情况已经被 $k=2$ 时包含了。

所以总共的时间复杂度为 $O(n^5+n^2\cdot2^{\lfloor \dfrac{n}{5}\rfloor})$。

Submission #270440681 - Codeforces