动态规划(2)：优先级队列优化

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为动态规划的优先级队列优化，包括连续 k 个数的最大值、最长递增子序列、最小制造成本等问题。

连续 k 个数中的最大值

问题描述

• 输入：数组 $a_1, a_2, \ldots, a_n$ 和 整数 $k$
• 输出：每个长度为 $k$ 的连续子数组中的最大值

DP 基本思路

• 暴力解法：对每个窗口遍历 $k$ 个元素找最大值，时间复杂度 $O(nk)$
• 堆优化：维护 $a_{i-k+1} \sim a_i$ 构成的堆，每次删除左侧元素，插入右侧元素，时间复杂度 $O(n \log k)$

双端队列优化

• 关键思路：维护一个单调递减队列（Potential Largest List），保存潜在最大值
• 队列性质：队首元素是当前窗口最大值，队列中元素按索引递增且值递减
• 更新步骤：
  • ​移除过期元素：若队首元素索引超出窗口左边界，弹出队首
  • ​维护单调性：从队尾开始，移除所有值小于当前元素 $a_i$ 的索引
  • 插入当前元素：将当前元素索引加入队尾
  • ​记录结果: 当 $i \ge k - 1$ 时，队首元素即为窗口最大值

• 时间复杂度：$O(n)$（每个元素入队、出队各一次）

最长递增子序列

问题描述

• 输入：序列 $a_1, a_2, \ldots, a_n$
• 输出：最长递增子序列长度（LIS）的长度，LIS 指 $a_{i_1} < a_{i_2} < \cdots < a_{i_k}$，其中 $i_1 < i_2 < \cdots < i_k$

优先级队列优化

• 核心思路：维护一个潜在前缀列表 sm，其中 sm[len] 表示长度为 len 的递增子序列的最小末尾值。由于该列表单调递增，查找过程可优化为二分搜索

• 算法步骤：

  • 初始化 $sm[0] = 0$
  • 对每个 $a_i$：
    • 二分查找使得 $a_i > sm[len]$ 的最大 $len$
    • 更新 $sm[len + 1] = a_i$
  • 输出更新过的最大 $len$

• 时间复杂度：$O(n \log n)$

最小生产成本

问题描述

• ​输入：生产成本 $a_1, a_2, \ldots, a_n$，
• 要求：将区间 $[i, j]$ 合并生产的成本为 $C + (\sum_{k=i}^{j} a_k)^2$
• ​输出：求最小总生产成本

DP 基本思路

• 子问题：f[i] 表示生产前 i 个物品的最小成本
• 状态转移：$f[i] = \min_{j < i} \{ f[j] + C + (\sum_{k=j+1}^i a_k)^2 \}$

凸包优化

• 为了维护潜在的分割点，我们需要知道计算 $f[i]$ 时，何时 $j=x$ 比 $j=y$ 更好
• 整理可得，

$$g(x, y) = \frac{(f[y] + s(y)^2) - (f[x] + s(x)^2)}{2(s(y) - s(x))} < s(i)$$

其中，$s(i) = \sum_{k=1}^{i} a_k$

• 维护凸包：

  • 用双端队列保存决策点对应的直线，保证相邻直线斜率单调递增
  • 当新增直线时，删除队尾斜率不满足单调性的直线

• 二分查找最优决策点：

  • 对每个 $i$，计算当前斜率 $s(i)$
  • 通过二分查找找到队列中斜率小于 $s(i)$ 相交的最优直线，得到最小 $f[i]$

整体算法

• 更新 f[i]

• 更新凸包

• 整体算法

• 时间复杂度：$O(n \log n)$

注：本文中所有图片均来自张宇昊老师的课程PPT。