总结
今天是 dp 专题。感觉好难。那就这样吧，开启新的一天吧！
决策单调性优化DP
四边形不等式优化 OI-WIKI
DP的决策单调性优化总结 --command_block
DP 优化方法大杂烩 --alex-wei
四边形不等式
考虑最简单的情形，我们要解决如下一系列最优化问题。
\[f(i) = \min_{1 \leq j \leq i} w(j,i) \qquad \left(1 \leq i \leq n\right) \tag{1} \]- 四边形不等式 ：如果对于任意 \(a\leq b\leq c\leq d\) 均成立
若 \(w\) 满足四边形不等式，则问题 (1) 满足决策单调性。
常见优化方式：分治，二分队列。
「POI2011」Lightning Conductor 分治，头尾各来一遍就好。要注意，计算代价的时候不能向上取整，否则会破坏四边形不等式的性质！
「HNOI2008」玩具装箱 toy 区间分拆问题，内部满足四边形不等式外面也一定满足，写出来就会发现 f 消掉了。顺序递推，只能用二分队列来写了，虽然分治更好写。这道题显然可以斜率优化来做，但是也具有决策单调性的性质。
这道题也能用斜率优化写，因此顺便写了一遍斜率优化。
区间分拆问题
\[f(k,i) = \min_{1\leq j\leq i} f(k-1,j-1)+w(j,i) \qquad (1\leq k\leq m,\ 1\leq i\leq n) \tag{2} \]若 \(w\) 满足四边形不等式，则对于问题 (2) 成立 \(\mathop{\mathrm{opt}(k-1, i)}\leq \mathop{\mathrm{opt}}(k,i) \leq \mathop{\mathrm{opt}}(k,i+1)\)。
若 \(w\) 满足四边形不等式，则问题 (2) 的最优解 \(g(k):=f(n,k)\) 是关于 \(k\) 的凸函数。
然后就引出了 wqs 二分。
区间合并问题
\[f(j,i) = \min_{j \leq k < i} f(j,k) + f(k+1,i) + w(j,i) \qquad (1\le j< i\le n) \tag{3} \]- 区间包含单调性 ：如果对于任意 \(a \leq b \leq c \leq d\) 均成立
则称函数 \(w\) 对于区间包含关系具有单调性。
若 \(w\) 满足区间包含单调性和四边形不等式，则状态 \(f(j,i)\) 满足四边形不等式。
若 \(w\) 满足区间包含单调性和四边形不等式，则问题 (3) 中最小最优决策 \(\mathrm{opt}(j, i)\) 满足
\[\mathop{\mathrm{opt}}(j,i-1) \leq \mathop{\mathrm{opt}}(j,i) \leq \mathop{\mathrm{opt}}(j+1,i). \qquad (j + 1 < i) \]
例题：
Ciel and Gondolas 经典的决策单调性。这道题不用快读 TLE。好恶心。
wqs 二分
参看第三篇博客。
注意：保证最小情况下，段数最大最小值对二分过程有影响！三点共线的情况。
最小度限制生成树 wqs二分，但可以不用。数组开小了调了半天。伤心。
动态dp
还是参看第三篇博客。
可以用 矩阵乘法 描述转移方程，定义广义矩阵乘法：
\[C_{i,j}=\bigoplus_{k=1}^n A_{i,k}\otimes B_{k,j} \]只需要满足 \(\bigotimes\) 具有结合律，且 \(\bigotimes\) 对 \(\bigoplus\) 有分配律，则存在结合律。
常见广义矩阵乘法有 \(\min , +\) 卷积，\(\max , +\) 卷积，\(\mathcal or,and\) 卷积。
P4719【模板】动态 DP 动态树分治 树链剖分+ \((\max,+)\) 矩阵维护。
后记
dp 可真是有趣呢！使我使我……今天张贝还是没有来，zrj 也生病了，邓老师下午也离开了……呜呜呜。希望他们平安无事。
太伤心了，不写诗了。
喜报：我能去线下参加 WC 啦！
标签：opt,13,12,不等式,leq,2023,四边形,单调,mathrm From： https://www.cnblogs.com/huasushis/p/17900198.html