复训时很好的字符串题

description

solution

考虑到这么一件事情，就是我最终的字符串 \(t\) 一定是由 \(s\) 的若干段前缀拼接而成，因为如果不是前缀，换成前缀一定不劣。

然后我们拥有一个朴素的状态 \(f_{i, j}\) 表示填到第 \(i\) 个数，且最后一段是由一段长度为 \(j\) 的前缀拼接成的最大贡献。

考虑转移，显然我们有 \(f_{i + 1, j + 1} = \max ( f_{i, j} + g_{j + 1} )\)，其中 \(g_{j + 1}\) 为一个关于 \(j + 1\) 的有关定值状物。但是明显不止这一种转移，注意到我们可以将 \([1, j]\) 的任意一段 border 拎出来进行转移，因为是 border，所以我的 border 仍然是一段前缀，符合状态设计，并且末尾去掉 border 仍然是一段前缀，即可转移。即 \(f_{i, nxt_j} = \max ( f_{i, j} )\)。

最后取一下 \(\max\) 即可。不难发现转移条件是充要的。