四边形不等式优化DP
1.概念 四边形不等式是对一个二元函数定义：w(l,r)w(l,r)w(l,r)。这里的w(l,r)w(l,r)w(l,r)可以看作价值，权值或着价格都可以。 对于任意a≤b≤c≤da\le b\le c\le da≤b≤c≤d ，若都有w(a,d)+w(b,c)≥w(a,c)+w(b,d)w(a,d)+w(b,c)\ge w(a,c)+w(b,d)w(a,d)+w(b,c)≥w(a,c)+w(b,d)，我们就称w(l,r)w(l,r)w(l,r)满足四边形不等式，可以简单记为：”交叉小于包含“。 同时有结论，对于a≤ba\le ba≤b，有w(a,b−1)+w(a+1,b)≤w(a,b)+w(a+1,b−1)w(a,b-1)+w(a+1,b)\le w(a,b)+w(a+1,b-1)w(a,b−1)+w(a+1,b)≤w(a,b)+w(a+1,b−1)。 结论：若两个函数之间满足四边形不等式，那么和也满足四边形不等式。 话说为啥叫四边形不等式： AD+BC≥AC+BDAD+BC\ge AC+BDAD+BC≥AC+BD，这个显然在初中是学过的。 反四边形不等式： 就是符号调换...
单调队列优化DP
0.前言 本文章例题出自于蓝书，优化方案来自许多博客（但我忘了呜呜呜） 1.单调队列概念与怎么优化 单调队列，我们先来看他是用来干什么的。 单调队列主要用于维护两端指针单调不减的区间最值。 ——oiwiki 对于一般的特殊DP方程，我们可以进行优化。 他优化的是下面的一类DP方程，其中： 得到的方程：f[i]=minL(i)≤j≤R(i)(f[j]+a[i]+b[j])\text{得到的方程：} f[i]=\min\limits_{L(i)\le j \le R(i)}{(f[j]+a[i]+b[j])} 得到的方程：f[i]=L(i)≤j≤R(i)min(f[j]+a[i]+b[j]) 因为i是外层循环定值，变形为：f[i]=minL(i)≤j≤R(i)(f[j]+b[j])+a[i]\text{因为i是外层循环定值，变形为：} f[i]=\min\limits_{L(i)\le j \le R(i)}(f[j]+b[j])+a[i] 因为i是外层循环定值，变形为：f[i]=L(i)≤j≤R(i)min(f[j]+b[j])+a[i] 其中min可以替换为...
斜率优化与WQS带权二分优化DP
1.前言 本文章图较多！ 动态规划在转移的时候，我们称最终转移过来的状态为决策点。 而对于斜率优化和WQS带权二分都是利用凸包和切线的概念来优化DP [!WARNING] 斜率优化和WQS带权二分几乎完全不同，请不要混淆！ 2.凸包与切线 2.1 凸包 凸包是什么呢？其实就是字面意思，一个凸起的小包，但是这个是描述图形的。如下图： 严谨来说，应当是其图形的切线斜率是具有单调性，其导函数f′(x)f'(x)f′(x)具有单调性。 但是在OI中一般凸包都不是光滑的，如下图。 但是也还是可以满足定义的即： 经过相邻两点的直线斜率有单调性 2.2 切线与一次函数 2.2.1 一次函数 y=kx+by=kx+b y=kx+b kkk：斜率 bbb：截距（yyy 轴交点） 2.2.2 切线 对于切线来说，不阐述概念，但是我们可以观察一下性质。 我们让一个固定斜率kkk的直线取切这个二次函数（也是个凸包） 发现什么？当恰好在切点时，截距bbb 最大，这是条基本也是条很重要的性质。 3. 斜率优化 3.1 k与x同单调 来做DP题。 nnn 个任务排...
