ARC058F_驱动网

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

ARC058F

2023-03-12 20:09:40 来源：博客园

(资料图片)

\(\mathcal{Link}\)

考虑暴力 DP，设 \(f_{i,j}\) 表示前 \(i\) 个串中长度为 \(j\) 的最优串。

注意到字典序具有良好的性质：对于有希望成为最优解的 \(f_{i,j}\) 和 \(f_{i,k}\)（\(j

考虑转移: \(f_{i,j}=\min(f_{i-1,j},f_{i-1,j-|a_i|}+a_i)\)。我们可以先算出 \(f_{i,j}\) 的值（只需要记录哪个转移更优就好了），然后用单调栈维护当前有用状态即可，最后可以由栈顶更新出 \(s_i\)。

所以我们具体要干的就是判断 \(f_{i,j}\) 和 \(f_{i,k}\) 的大小。发现每个 \(f_i\) 都是由 \(f_{i-1}\) 和 \(s_i\) 拼成的，所以可以使用 Z 函数算出 \(\operatorname{lcp}\) 即可快速判断，实在不会可以用哈希。

复杂度 \(\mathcal O(nm+\sum |s|)\)

关键词：