数据结构优化 DP

David_Mercury · 2023-07-11 16:21:34 · 个人记录

一、概念 \& 思想

对于一个状态，如果它策略集合的选取满足一个简单的不等式，我们就可以使用数据结构对这个范围进行维护。

二、应用

• 变量维护

  变量可以维护的仅限于范围单调递增不减。

  • LCIS

• 单调队列维护

  单调队列可以维护的序列需要满足上下界都单调移动这一条件。
  两种得到优化的方法：通过数学推导，拆分出仅与决策状态 k 相关的，以及仅与阶段 i 和当前状态 j 相关的两部分；或者直接运用贪心。
  以上方法都为保证，不管 j 如何变化，队内决策的相对大小不会变化。
  需要注意的一点是，对于部分毒瘤题目，最好手写双端队列。

  • P4544 [USACO10NOV] Buying Feed G
    这是一道基于数学拆分的单调队列优化。
    一眼背包，最开始直接设 f[i][j] 表示在 i 店时有 j 吨饲料。决策即枚举 f[i'][j']。此时为 O(K^2 N^2) 。
    在每个店购买饲料的消耗是独立的，因此我们不需要关心在何处购买的。可以将 f 简化为 f[j]。复杂度简化为 O(K^2 N)。
    因为唯一可能卡过的复杂度是 O(KN)，猜想到可能要使用单调队列优化。再推导一波，分解出两部分即可。

  • P3572 [POI2014] PTA-Little Bird
    重点在于对贪心的运用，有点像这道题。明明是求与 x 的大小关系，但若 y > z，则 z > x 总可以推出 y > x，则选 y 一定更优。
    如何想到这一点呢？大概只有根据数据范围所要求的线性复杂度猜测其为单调队列优化，再寻找有无在入队之时就可以确定的策略优劣关系。

  • P5665 [CSP-S2019] 划分 \& P4954 [USACO09OPEN] Tower of Hay G
    这两道题也是结合贪心的，而且结论一模一样：使前后两个划分段的差尽量小。但是接下来的单调性证明还是要运用数学推导。

  • P6563 [SBCOI2020] 一直在你身旁
    很好的一道题。
    首先，需要列出区间 dp 方程。
    接着，关注 a_i 单调递增这一条件，运用贪心：“右半边”大于“左半边”的情况不优，仅有最小的“右大左”有可能更新答案。将重心聚焦到左半边问题上。
    另外一点贪心：在一个端点固定不动时，范围越大，f[l][r] 越大。因此，如果 l 或 r 固定不动，决策点 k 的选取呈现单调性。
    然后我们就试着以固定 l 或 r 来进行区间 dp。区间 dp 中阶段 len 不完全必要，它的最低要求仅为小区间先于大区间更新。具体来说：无论将 l 还是 r 放到外层，只用满足 l 从大到小，r 从小到大。

  • 多重背包
    可以发现，如果 x, y 模 v_i（物品体积）不同余，那么二者的决策集合互不相干。而每一个同余系内的决策转移满足单调队列优化的要求。由此可达到复杂度 O(nm)。

• 其他数据结构维护

  一般来说，我们通过循环限制不等式关于下标的一侧，再通过复杂一点的数据结构解决不规则的另一侧。

  • 树状数组：P4303 [AHOI2006] 基因匹配，f[i] = \max^i_{j=1} f[j]（i 不一定单调、平滑递增）

  • 权值树状数组：P3970 [TJOI2014] 上升子序列 \& The Battle of Chibi，f[i] = \max_{1 \le j \le i, a_j < a_i} f[j]

  • 线段树：P4644 [USACO05DEC] Cleaning Shifts S, f[i] = \max^{r_i}_{j = l_i} f[j]