凸四边形不等式优化dp

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

理论篇

决策单调性

对于一类一维$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 $\mathrm{并}\mathrm{假}\mathrm{定}$pro[i][j]$\mathrm{为}\mathrm{到}$dp[i][j]$\mathrm{的}\mathrm{最}\mathrm{优}\mathrm{转}\mathrm{移}$k$,\mathrm{如}\mathrm{果}$pri[i][j]$\mathrm{关}\mathrm{于}$i$\mathrm{单}\mathrm{调}，\mathrm{且}\mathrm{关}\mathrm{于}$j$\mathrm{单}\mathrm{调}，\mathrm{那}\mathrm{么}\mathrm{我}\mathrm{们}\mathrm{称}\mathrm{该}$dp$具有决策单调性。

四边形不等式

对于二元数论函数，$w(i,j)$，若满足$a\le b\le c\le d$恒有 $w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$则该二元函数满足四边形不等式

他的充要条件是: 若$a<b$ 恒有$w(a,b)+w(a+1,b+1)\ge w(a,b+1)+w(a+1,b)$

可以理解为，交叉小于包含

区间包含单调性

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

新增定义

如果存在转移$dp[j]\to dp[i]$不管此转移是否最优，我们都把$j$叫做一个决策点。

强化的决策单调性：对于某一维$dp$，如果在某决策点集合中，若$x$为到$dp(i)$的最优决策，则对于所有的大于$i$的$j$，$x$依旧是此决策点集合中的最优决策。 二维同理。

证明

一维DP

考虑转移式$dp[i]=min(dp[j]+w(j,i))$，其中$1\le j<i$ ，且函数$w$满足四边形不等式

不妨假设$p_x$是$dp[x]$的最佳转移之一，$p$是一个$dp[x]$的任意一个转移

则$\mathrm{\forall }p<x$ 都有$dp[p_x]+w(p_x,x)\le dp[p]+w(p,x)$ 即 $dp[p_x]-dp[p]\le w(p,x)-w(p_x,x)$

根据四边形不等式，$p{p}_{x}xy$ 都有$w(p,y)+w(p_x,x)\ge w(p,x)+w(p_x,y)$ 即$w(p,x)-w(p_x,x)\le w(p,y)-w(p_x,y)$

合并上面两个不等式得到了$dp[p_x]-dp[p]\le w(p,y)-w(p_x,y)$ 即$dp[p_x]+w(p_x,y)\le dp[p]+w(p,y)$, 根据这个不等式，我们发现他说明了这样一个事实，即:

如果$p_x$是$dp[x]$的最佳转移之一，则$\mathrm{\forall }p\le p_x\le x\le y$，对于$dp[y]$都有决策点$p_x$优于$p$

二维DP较复杂

需要对每一纬单独证明决策单调性，其中涉及到$w$函数的四边形不等式性质和$dp$自身的四边形不等式性质，此处不做证明，实战中也不会遇到，决策单调性需要依靠敏感的直觉，你需要用最快的速度猜测决策点单调，然后用一两分钟编写程序验证其单调性。

做法篇

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

当此$dp$满足强化的决策单调性的时候，我们可以用单调队列来优化$dp$,此单调队列维护一个数据结构，该数据结构维护一个决策数组,当我们处理$dp[i]$的时候，该数组维护了$dp[i]$到$dp[n]$的在$[1,i)$中的最优决策点。 显然该决策数组单调增，我们拿出最优队首，为$dp[i]$赋值，下一步应该是更新该决策数组，怎么更新呢，我们二分即可。 ## 用二分更新决策数组 先证明,对于新加进来的决策，对于旧决策数组的影响具有单调性，即存在一个分界点，分界点左边，新决策不如旧决策，分界点右边，新决策优于旧决策， 首先，我们假设新决策的影响不具有单调性，即新决策的影响杂乱无章，在这种情况下，我们取出靠左边的决策为新决策的元素的下标，根据强化的决策单调性，此元素右边的 元素的当前最优决策值必须且只能为$i$，因为当前大于等于i的决策只有$i$。矛盾发生，故新决策的影响具有单调性。

当于是我们二分出这个点即可解决 ，

单调队列优化

为什么我们要用单调队列呢，我们先考虑，如果我们采取线段树优化，那么更新决策数组显然是$lg$级别的，但是 二分新决策边界的时候，复杂度为$lg\ast lg$，因为单点查询是$lg$级别的，再加个二分就双$lg$了。

为了时间复杂度好写，我们采取单调队列来维护，单调队列维护一个三元组分别是决策点和目前以此决策点为最优决策的$dp$，因为这是个区间，所有要用两个数来维护。

更新的时候，直接修改队尾的三元组即可，查询的时候，暴力枚举队尾的三元组，如果新决策完全不如旧决策， 此次修改结束，如果队尾的决策完全不如新决策弹掉了队尾，修改新队尾的区间为后缀区间，继续枚举，如果新决策优于队尾决策的一部分，二分出位置后直接修改即可。

很容易证明单调队列优化的时间复杂度是$lg$的，优于线段树。

决策单调性优化二维dp

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

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

对于一维$dp[i]=min/max(dp[j]+w(i,j)) $,\mathrm{若}w\mathrm{满}\mathrm{足}\mathrm{四}\mathrm{边}\mathrm{形}\mathrm{不}\mathrm{等}\mathrm{式}\mathrm{则}，\mathrm{此}$dp$满足决策单调性,并且，满足强化的决策单调性。

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