凸四边形不等式优化dp

决策单调性算法竞赛进阶指南

对于一类一维dp,若有转移dp[i]=min\max(dp[j]+w(i,j)) 0<j<i，并假定pri[i] 为到dp[i]的最优转移j，如果pri[i]关于i单调，那么我们称该dp具有决策单调性。
对于一类二维dp,如果有转移dp[i,j]=min\max(dp[i][k]+dp[k+1][j]+w(i,j)) i<=k<j 并假定pro[i][j]为到dp[i][j]的最优转移k,如果pri[i][j]关于i单调，且关于j单调，那么我们称该dp具有决策单调性。

新增定义

如果存在转移dp[j]->dp[i]不管此转移是否最优，我们都把j叫做一个决策点。
强化的决策单调性：对于某一维dp，如果在某决策点集合中，若x为到dp(i)的最优决策，则对于所有的大于i的j，x依旧是此决策点集合中的最优决策。二维同理。

强化的决策单调性优化一维dp

当此dp满足强化的决策单调性的时候，我们可以用单调队列来优化dp,此单调队列维护一个数据结构，该数据结构维护一个决策数组,当我们处理dp[i]的时候，该数组维护了dp[i]到dp[n]的在[1,i)中的最优决策点。显然该决策数组单调增，我们拿出最优队首，为dp[i]赋值，下一步应该是更新该决策数组，怎么更新呢，我们二分即可。

用二分更新决策数组

先证明,对于新加进来的决策，对于旧决策数组的影响具有单调性，即存在一个分界点，分界点左边，新决策不如旧决策，分界点右边，新决策优于旧决策，首先，我们假设新决策的影响不具有单调性，即新决策的影响杂乱无章，在这种情况下，我们取出靠左边的决策为新决策的元素的下标，根据强化的决策单调性，此元素右边的元素的当前最优决策值必须且只能为i，因为当前大于等于i的决策只有i。矛盾发生，故新决策的影响具有单调性。
当于是我们二分出这个点即可解决，

单调队列优化

        为什么我们要用单调队列呢，我们先考虑，如果我们采取线段树优化，那么更新决策数组显然是lg级别的，但是二分新决策边界的时候，复杂度为lg*lg，因为单点查询是lg级别的，再加个二分就双lg了。
        为了时间复杂度好写，我们采取单调队列来维护，单调队列维护一个三元组分别是决策点和目前以此决策点为最优决策的dp，因为这是个区间，所有要用两个数来维护。
        更新的时候，直接修改队尾的三元组即可，查询的时候，暴力枚举队尾的三元组，如果新决策完全不如旧决策，此次修改结束，如果队尾的决策完全不如新决策弹掉了队尾，修改新队尾的区间为后缀区间，继续枚举，如果新决策优于队尾决策的一部分，二分出位置后直接修改即可。
        很容易证明单调队列优化的时间复杂度是lg的，优于线段树。

决策单调性优化二维dp

这个就特别简单了，dp[i][j]的转移在dp[i][j-1]和dp[i+1][j]之间枚举即可。

四边形不等式

        对于二元数论函数，w(i,j)，若满足a<=b<=c<=d恒有 w(a,d)+w(b,c) >=w(a,c)+w(b,d)则该二元函数满足四边形不等式
        他的充要条件是: 若a<b 恒有w(a,b+1)+w(a+1,b)>=w(a,b)+w(a+1,b+1)
        可以理解为，交叉和大于包含和

区间包含单调性

对于二元数论函数，i<j的w(i,j) 我们将参数看做区间，定义区间的包含为偏序关系，若w的值关于该偏序关系单调，则称该函数具有区间包含单调性。

什么时候可以使用这些优化？

对于一维dp[i]=min\max(dp[j]+w(i,j)) ,若w满足四边形不等式则，此dp满足决策单调性，并且，满足强化的决策单调性。
对于二维dp[i,j]=min\max(dp[i][k]+dp[k+1][j]+w(i,j)) 若w满足四边形不等式，且w满足区间包含单调性，则dp满足四边形不等式，且具有决策单调性。