『动态规划的单调性优化』

动态规划的单调性优化

1. 决策集合优化

\(\mathrm{dp}\)的时候决策集合只扩大不减小，直接把最大值\(/\)最小值\(/\)累加和记下来就好了.

例如：\(\mathrm{LCIS\ CH5101}\)，\(f_{i,j}=\max\limits_{0\leq k

外层\(i\)不变，随着\(j\)增大，每次决策\(k\)最多增加一个，判断一下是否合法记下来即可.

2. 单调队列优化

\(\mathrm{dp}\)的时候决策区间上下界都单调变化，可以直接记录区间和的值. 如果是最优化\(\mathrm{dp}\)，那就要用滑动窗口记录区间最值.

写代码的时候，在循环开始的时候排除队首过期决策，然后取队首作为最优解，然后加入新决策. 有些边界麻烦的初值可以暴力算掉.

多重背包怎么用单调队列优化？先写方程：\(f[j]=\max\limits_{1\leq k\leq c_i}\{f[j-k\times v_i]+k\times w_i\}\).

观察：决策点每次位移\(v_i\)，那就把\(j\)按照\(v_i\)的余数分类. 设\(j=u+v_i\times p\)，于是：

\[f[u+v_i\times p]=\max\limits_{\max\{0,p-c_i\}\leq k\leq p-1}\{f[u+v_i\times k]+(p-k)\times w_i\}
\]

这样的话可以把\(i,u\)当成定值，枚举\(p\)，此时决策变量\(k\)的上下界单调变化，就可以用单调队列了.

3. 斜率优化

多项式\(v(i,j)\)含有\(i,j\)乘积项的\(1D/1D\)动态规划，一般可以用单调队列维护下凸壳\(/\)上凸壳.

设\(f_i=\max\limits_{0\leq j\leq i-1}\{f_j+A(i)+B(j)+p(i)q(j)\}\)，然后移项一下：

\[f_j+B(j)=-p(i)q(j)-A(i)+f_i
\]

这时候把所有决策点\(j\)看成平面上的点\(P_j(-q(j),f_j+B(j))\)，那么现在你要用一条斜率为\(p(i)\)的直线去切这些点，求最小截距.

一般来说，这些点都是单调递增的，所以我们可以用单调队列维护下凸壳作为最优决策集. 如果\(p(i)\)也是单调的，只要在队首操作最优决策即可，如果\(p(i)\)不单调，那就二分找最优决策点.

如果这些点不是单调递增的话，那就要用平衡树\(/\)\(\mathrm{cdq}\)分治维护凸壳. 不过用李超树求一次函数最值会更简单.

注意事项有点多：

4. 四边形不等式

直接记结论即可：对于整数域上的二元函数\(w(x,y)\)，若其满足：

\[a\leq b\leq c\leq d,w(a,d)+w(b,c)\geq w(a,c)+w(b,d)
\]

或者

\[a\]

则称\(w\)满足四边形不等式.

对于\(f_i=\min\limits_{0\leq j

暴力优化的话直接从上一个决策点开始枚举即可，如果用队列维护决策点连续段可以做到\(O(n\log_2 n)\)，需要用二分找分界点. 如果是二维的\(\mathrm{dp}\)，每次仅从上一维转移，可以采用分治写法，时间复杂度也是每层\(O(n\log_2 n)\)，如果一维\(\mathrm{dp}\)强行套\(\mathrm{cdq}\)分治的话，时间复杂度两个\(\log\).

对于\(f_{i,j}=\min\limits_{i\leq k

\[\forall i

按照长度为阶段的区间\(\mathrm{dp}\)，直接在决策范围里面枚举时间复杂度就优化到\(O(n^2)\).

习题：

\(\mathrm{BZOJ}4709\) 柠檬

\(\mathrm{CF868F\ Yet\ Another\ Minimization\ Problem}\)

\(\mathrm{CF321E\ Ciel\ and\ Gondolas}\)

任务安排\(4\)