Description
给定一个长度为 n 的字符串 s,现在有一个打字机,每次你可以花费 a 的代价打出一个字符,或者花费 b 的代价打出一个 已经打出的字符串 的子串,求打出 s 的最小代价。(1≤n,a,b≤5×103)
Source
Solution
很容易想到 O(n3) 的 DP 。
我们用 fi 表示打完前 i 个字符所需要的最小代价,状态转移方程为
fi=min(fi−1+a,min{fi−k}+b)考虑第 i 个字符是怎么打出来的。
可以先打出前 i−1 个字符,然后花费 a 的代价打出第 i 个字符。
设子串的末尾为第 j 个字符,子串的长度为 k,则可以先打出前 i−k 个字符,再花费 b 的代价打出 k 个字符。前提是 si−k+1,i 与 sj−k+1,j 相等,可以用 hash 判断。
最后取上述两种情况的最小值即可。
如何优化?
不难发现,f 数组的值其实是单调不减的。
换句话说,方程中 k 的值要尽可能大。
而 k 的最大值其实是 s1,i 与 s1,j 的 最长公共后缀 长度。
于是我们可以省去对 k 的枚举,同样的状态,新转移方程为
fi=min(fi−1+a,min{fmax(i−LPSi,j,j)}+b)其中 LPSi,j 表示 s1,i 与 s1,j 的最长公共后缀长度。之所以要与 j 取 max,是因为已经假设子串末尾为第 j 个字符,i−LPSi,j 的值肯定不能比 j 小,否则就等于取了 还没打出来的字符串 的子串。
图示:
LPS(最长公共后缀) 可以用 O(n2) DP 预处理,考虑第 si 和 sj 是否相等即可。
LPSi,j={LPSi−1,j−1+1(si=sj)0(si≠sj)当然这道题也可以用 SA(后缀数组) 维护 DP,只不过写起来麻烦一点。
总时间复杂度为 O(n2) 。
Code
1 |
|
Gitalking ...