简要题意：你需要打出一个长度为 \(n\) 的字符串 \(s\)。
- 花费 \(c_1\) 的代价，在末尾打出一个字符。
- 花费 \(c_2\) 的代价，在末尾打出目前已打出字符串的某个子串。
问最少的操作代价，\(n\le5\times10^3\)。
不妨用 \(f_i\) 表示操作前 \(i\) 个数的最小代价。可以在枚举当前点 \(i\) 时再枚举一个之前点 \(j\)。如果 \(\exist\space1\le l\le r\le j,a[j+1\dots i]=a[l\dots r]\) 就进行一次转移。暴力去判断子串相等就是 \(\mathcal O(n^3)\) 的复杂度。
可以配合 \(\text{hash}\)，还要线段树维护 set。第 \(i\) 个 set \(s_i\) 储存 \(\{x|x=a[p\dots i],1\le p\le i\}\) 的 \(\text{hash}\) 值，查询相当于在一段前缀 set 中查询一个元素是否存在。不过这样又要用线段树又需要 set，复杂度 \(\mathcal O(n^2\log^2n)\)，就算使用 unordered_set 还得承受大常数 \(\mathcal O(n^2\log n)\)。
发现不管怎么做，询问的东西都是一样的，先预处理出所有询问，按照每个询问的 \(i\) 排序。这样每次询问都在一段前缀中进行。排序询问的复杂度是 \(\mathcal O(n^2\log n)\)，后续查询采用 unordered_set，复杂度 \(\mathcal O(n^2)\)。总复杂度为 \(\mathcal O(n^2\log n)\)。
也可以维护原串的最长公共后缀，由于 \(f\) 具有单调性（假如 \(f_i>f_{i+1}\) 必然是操作 \(2\) 使得这种情况发生，那我操作 \(2\) 少粘贴一个字母就能使得 \(f_i=f_{i+1}\)，也就是说假设必然不成立，\(f\) 具有单调性，\(f_i\le f_{i+1}\)），每次应该从最小的 \(j\) 转移过来，这个最小的 \(j\) 就是之前某个 \(j\) 与 \(i\) 的最大公共后缀。复杂度 \(\mathcal O(n^2)\)。
在这个做法的基础上，在后缀自动机上跑双指针（\(i\) 和 \(j\)），\(a[j\dots i]\) 存在就转移，否则 \(j\) 右移。复杂度 \(\mathcal O(n)\)。