题意理解

我们有一个文本编辑器，初始时屏幕内容 ( X ) 和剪切板内容 ( Y ) 都为空。
可以执行三种操作：

• 操作 A（花费 (A)）：在 (X) 末尾输入一个字符。
• 操作 B（花费 (B)）：将 (X) 复制到 (Y) 并清空 (X)（全选并剪切）。
• 操作 C（花费 (C)）：将 (Y) 粘贴到 (X) 末尾。

目标：用最少的总时间输入给定的字符串 ( S )（长度 ( N \le 2500 )）。

核心难点

直接枚举所有可能的操作序列不可行，因为操作序列长度可能很长，而且可以多次复制粘贴不同子串。
我们需要找到一种方式，将问题建模为 动态规划，并利用字符串结构进行优化。

主要思路

1. 状态设计

设 ( dp[l][r] ) 表示生成 ( S[l:r] )（即子串从 (l) 到 (r)，索引从 1 开始）的最小花费。

最终答案就是 ( dp[1][N] )。

2. 状态转移

(1) 直接输入

最朴素的方式是一个个字符输入： [ dp[l][r] = \min(dp[l][r],\ dp[l][r-1] + A) ] 即先构造好 ( S[l:r-1] )，再输入最后一个字符 ( S[r] )。

(2) 粘贴操作

如果 ( S[l:r] ) 可以通过一次粘贴得到，那么它必然是由某个更早生成的子串 ( S[k:m] ) 复制到剪切板，然后粘贴到当前字符串末尾形成的。

具体来说，假设我们在构造 ( S[l:r] ) 时，最后一次操作是粘贴一个子串 ( t )（即剪切板内容），那么 ( t ) 必须是 ( S[l:r] ) 的一个后缀，并且 ( t ) 在之前已经出现在字符串的某个位置。

更精确地，如果存在 ( k < l ) 使得 ( S[k:k+len-1] = S[r-len+1:r] )（其中 ( len = r-l+1 ) 吗？不，这里 ( len ) 是粘贴的串长），那么我们可以：

• 先构造 ( S[l:r-len] )（花费 ( dp[l][r-len] )）
• 然后执行一次粘贴（花费 ( C )）
• 并且之前要有一次剪切操作（花费 ( B )）来把 ( t ) 放入剪切板

但要注意：剪切操作可以在构造 ( t ) 之后立即做，也可以在更早的时候做，只要粘贴时剪切板里是 ( t ) 就行。

3. 更通用的区间 DP 转移

更系统地，考虑区间 ([l,r])：

1. 直接输入末尾字符： [ dp[l][r] = \min(dp[l][r],\ dp[l][r-1] + A) ]

2. 从剪切板粘贴一个子串： 假设我们粘贴的子串长度为 ( L )，且 ( S[r-L+1:r] ) 在 ( S[l:r-L] ) 中出现过（位置 ( p ) 满足 ( S[p:p+L-1] = S[r-L+1:r] ) 且 ( p \le r-L )），那么我们可以：

   • 先构造 ( S[l:r-L] )（花费 ( dp[l][r-L] )）
   • 执行一次粘贴（花费 ( C )） 但之前必须执行一次剪切，把该子串放入剪切板。剪切可以在构造该子串之后的任意时刻做，但为了最小化花费，我们会在构造好该子串后立刻剪切（花费 ( B )），因此总花费为： [ dp[l][r] = \min(dp[l][r],\ dp[l][r-L] + C + \min_{p} dp[p][p+L-1] + B) ] 这里 ( \min_{p} dp[p][p+L-1] ) 表示生成这个子串的最小花费（因为我们要先构造它才能剪切）。

4. 优化查找相同子串

我们需要快速知道：对于给定的 ( L ) 和 ( r )，是否存在 ( p < r-L+1 ) 使得 ( S[p:p+L-1] = S[r-L+1:r] )。

可以用 字符串哈希 预处理所有子串的哈希值，然后对每个长度 ( L ) 和每个起始位置，记录之前是否出现过相同子串。

或者用 Z 算法 / KMP 来找到每个子串的最早出现位置。

5. 最终算法复杂度

• 状态数 ( O(N^2) )
• 对每个状态，我们可能需要枚举粘贴的串长 ( L )，以及检查该串是否之前出现过
• 通过预处理，可以做到 ( O(1) ) 判断，因此总复杂度大约 ( O(N^3) ) 会超时，需要进一步优化
• 实际优化：我们不需要枚举所有 ( L )，只需枚举那些在 ( S[1:r-1] ) 中出现过的 ( S[r-L+1:r] ) 即可，这可以用后缀自动机或后缀数组加速，最终目标 ( O(N^2) )

总结

这道题是一个典型的 区间 DP + 字符串匹配优化 问题。
关键点在于将复制粘贴操作转化为对子串重复出现的利用，并用动态规划状态记录生成每个子串的最小代价。

由于 ( N \le 2500 )，( O(N^2) ) 的算法是可接受的，但需要精细实现以避免 ( O(N^3) ) 的暴力枚举。