四边形不等式优化DP
定义
1.原始定义
假设有一个二元函数(w(x,y))，如果对于任意(a leq b leq c leq d)，有
就说函数(w)满足四边形不等式
2.等价定义
还有一个等价的定义：如果对于任意(aleq b)，有：
就说函数(w)满足四边形不等式、
证明 2 -> 1
对于任意(a < c)， 有 ((1))式：
对于任意(a+1, c)，有((2))式：
两式相加得到((3))式：
对比((1))式和((3))式，发现(a + 1)可以扩成(a + 2)，同理(a+2)可以扩成(a+3)，(a+3)可以扩成(a+4)……可以一直扩大直至(bleq c)（(b)是在(a)和(c)之间的一个数），从而得到：
同理，对于任意(a<c+1)，有((4))式：
((1))式与((4))式相加得到((5))式：
与((1))式进行一下直观对比：
((1))式：(w(a, c + 1) + w(a + 1, c) geq w(a, c) + w(a + 1, c + 1))
((5))式：(w(a, c + 2) + w(a + 1, c) geq w(a, c) + w(a + 1, c + 2))
可以发现(c+1)可以扩成(c+2)，同理(c+2)可以扩成(c+3)，(c+3)可以扩成(c+4)……可以一直扩大一直到(d(cleq d))，从而得到：
再把上式(a+1)扩大到(b)，保证(aleq b leq c leq d)，就可以得到(1)，即
(w(a,d) + w(b, c) geq w(a, c) + w(b, d))
由此原始定义得证。
所以，证了这么久有啥用呢？
决策单调性
我们在做(DP)时经常会遇见这样的(DP)方程
这样的(DP)方程被称作(1D/1D)动态规划，(cost(i,j))决定着优化策略选择
决策单调性定理
如果函数(cost(i,j))满足四边形不等式，则(dp[i])有决策单调性（充分条件）
证明：
注：假设此时已经满足四边形不等式
假设此时的(DP)方程为(dp[i] = min{dp[j] + cost(j, i)})，(dp[i])的决策点是(p[i])，对于(j < p[i] - 1(j < i))，根据最优性：
假设(i' > i)，此时(j leq p[i] leq i leq i')，根据四边形不等式：
对这个式子进行移项，得到
将此式和(DP)式（根据最优性得出的式子）相加得：
由此可得，对于(i')来说，(p[i])比(j)优，得证。
小小结
在上面的证明中我们可以知道，等价定义可以推出原始定义，而原始定义又可以推出决策单调性定理，其实在日常做题中，如果满足了等价定义，我们就可以直接用决策单调性来解决问题（就是说(2)可以推出(1)，(1)可以推出(3)，那么(2)可以推出(3)）
下面就来看一道例题吧
例题
链接：洛谷P3515 [POI2011]Lightning Conductor
题目很简洁，就是为了找这么一个数(p)满足题目中给出的式子
那么我们不妨先移项，得到如下的式子
而此时我们又要找到满足条件的最小的(p)
所以此时的(p)只要等于后面这个式子的最大值即可，即
先考虑一种比较好的情况，假设(j<i)，那么绝对值就可以去掉了，即
上式中(max)里的式子取到最大值，相当于负的这个式子取到最小值
所以我们可以定义(dp[i] = min(-a[j] - sqrt{i - j}))
为什么要用(min)呢，因为在上面的证明中我们使用的都是(min)，所以这里是用(min)，如果是(max)的话可以换成负数取个(min)就好了，这是一样的，反正(dp[i])是自己定义的，定义成正负都一样
但是这样直接做是(n^2)的，这不能达到我们的要求，所以现在我们来进行优化
观察一下这个(DP)方程的二元函数，那么此时的(w(j,i))就等于(-a[j] - sqrt{i - j})
为了进行优化，下一步我们证明一下这个(DP)能不能满足决策单调性
求证：(w(j, i+ 1) + w(j + 1, i) geq w(j, i) + w(j + 1, i + 1))
证明：
把式子展开得
发现可以去掉带有(a)数组的部分，然后式子就变成了这样
移一下项得
令(x = i - j)，因为(i > j) ，所以(x>0)，于是一开始那个繁琐的问题就变成了证明(sqrt{x} - sqrt{x - 1} geq sqrt{x + 1} - sqrt{x})
定义函数(f(x)=sqrt{x} - sqrt{x - 1})，问题又转化成了证明(f(x) geq f(x + 1))，那么就是要证明(f(x))是单调非递增的函数即可
懒得证单调性……自己搜吧(qwq)
因为是个单调递减函数，所以证明成功
(j>i)时可以把序列翻转，得到的结果是一样的，做题的时候将序列翻转反向再做一遍上述操作即可，就不证明了
代码鸽了
总结
因为我很辣鸡，所以只能写这么一点点了(qwq)
下面几个参考都可以去看一下，我大部分的思路全来自这里
另外给大家推荐几道题8
决策单调性优化模板题，但是会卡精度
可以用四边形不等式优化来做，也有一些很(np)的做法
上面那道题的加强版