单调队列优化dp

一、1D/1D动态规划

• 有一些动态规划，有着状态数为O(n)，每一个状态决策量为O(n)的动态规划方程。
  直接求解的时间复杂度为O(n^2)，这便是1D/1D动态规划。绝大多数这样的方程通过合理的组织与优化都是可以优化到O(nlogn)乃至O(n)的时间复杂度。

二、dp优化之单调队列优化

• 在1D/1D动态规划中，有一种dp，转移方程一般为：

$dp[i]=min(f[j])+g[i],(l[i]<=j<=r[i]),其中l[i]到r[i]的序列单调递增（不减）$

• 这样的dp可以用单调队列进行优化。

• 维护方式分为4步：

  • 1.将小于$l[i]$的所有$j$从队首剔除$(j>=l[i])$。
  • 2.采用队首的$j$对$dp[i]$赋值。
  • 3.将新的元素加入队尾$(j<=r[i])$。
  • 4.以某种策略维护队列单调。
• 例题：
  • 最大子序和
  • Sliding Window
  • 修剪草坪
    • 修剪草坪题解
  • 股票交易
• 作业：
  • 奶牛的跳格子游戏
  • 架设电话线
  • 跳房子

三、多重背包的单调队列优化

• 不考虑优化的多重背包状态转移方程：$f[j]=max(f[j-k\ast v[i]]+k\ast w[i])$
  考虑一个体积$j$，它的决策空间，只会是与他同余的体积点
  在这个决策空间中，决策范围是单调的，有点类似单调队列，可以进行单调队列优化
  考虑设$j=k\ast v[i]+u$
  则$f[p\ast v[i]+u]=max(f[k\ast v[i]+u]+(p-k)\ast w[i])$
  有$f[p\ast v[i]+u]=max(f[k\ast v[i]+u]-k\ast w[i])+p\ast w[i]$
  这个式子右边前面在枚举$k$时，外循环$i,u$是固定值，所以式子的值只和
  $k$有关，由于$k$是单调的，所以维护一个$f[k\ast v[i]+u]-k\ast w[i]$的单调队列即可