问题求解II-HW14 题解
Problem A: 最长公共子序列
- 给定两个字符串 $s, t$，求两者的最长公共子序列的长度。
- $1\leq |s|\leq 10^6, 1\leq |t|\leq 10^3$。
见 这份题解。
Problem B: 写作文
- 给定长度为 $n$ 的数列，现可以挑选 $k$ 个数加 $x$，剩下的数减 $x$。问在最优操作下，数列的最长连续子序列和是多少。
- $n\leq 10^5$。
考虑对于每一个右端点寻找最优的(即能使连续子序列之和最大的)左端点。尝试写出区间 $(l, r]$ 最优修改后的区间和表达式：
$$ sum(l, r) = \begin{cases} s_r - s_l + x(r - l)= (s_r+xr) - (s_l + xl)&, r - l \leq k \\ s_r - s_l + xk - x(r - l - k) = (s_r - xr) - (s_l + xl) + 2xk &, r - l > k \end{cases} $$
其中 $s_i$ 表示前 $i$ 个数原始的和。容易发现，左端点在两个式子中相关的项只有 $s_l + xl$，即左端点的选择和右端点的位置无关。因此对于每一个右端点 $r$，我们只需在 $[1, r-k]$ 和 $(r-k, r]$ 两个区间中分别挑选 $s_l + xl$ 值最小的端点作为备选左端点更新答案即可。
$[1, r-k]$ 这个区间处理起来相对容易，可以在枚举右端点的同时维护前缀最小值；$(r-k, r]$ 这个区间处理起来稍微麻烦一些。使用堆等数据结构是一种方法，不过利用单调性可以将这个问题做的更好。这个单调性指的是：从左向右枚举右端点时，如果 $l_1<l_2$ 且 $s_{l_1}+xl_1>s_{l_2}+xl_2$，那么 $l_2$ 一定优于 $l_1$。这是因为 $l_2$ 不仅好而且位置更右，可以服务更多的后续右端点。凭借这个性质，我们可以用一个双端队列维护 $(r-k, r]$ 区间内值递增的一系列位置，每次从队头取最优左端点，在队尾添加新的端点并更新队列。总时间复杂度为 $O(n)$。