设$w(x,y)$是定义在整数集合上的二院函数。若对于定义域上的任意整数$a,b,c,d$，其中$a\le b\le c\le d$，都有$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$成立，则称函数$w$满足四边形不等式。

定理

设$w(x,y)$是定义在整数集合上的二元函数。若对于定义域上的任意整数$a,b$，其中$a<b$，都有$w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)$成立，则函数$w$满足四边形不等式。

证明

对于$a<c$，有$w(a,c+1)+w(a+1,c)\ge w(a,c)+w(a+1,c+1)$

对于$a+1<c$，有$w(a+1,c+1)+w(a+2,c)\ge w(a+1,c)+w(a+2,c+1)$

两式相加，得到$w(a,c+1)+w(a+2,c)\ge w(a,c)+w(a+2,c+1)$

以此类推，对于任意的$a\le b\le c$，有$w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)$

同理，对任意的$a\le b\le c\le d$，有$w(a,d)+w(b,c)\ge w(a,c)+w(b,d)$

决策单调性

在状转方程$f[i]=\min\{f[j]+w(j,i)\},j\in[0,i)$中，若函数$w$满足四边形不等式，则$f$具有决策单调性。

证明

定义$p[i]$表示$i$的最优决策点。

$\forall i\in[1,n],\forall j\in[0,p[i]-1]$，根据$p[i]$为$i$的最优决策点，则有

$$f[p[i]]+w(p[i],i)\le f[j]+w(j,i)$$

$\forall i'\in[i+1,n]$，因为$w$满足四边形不等式，则有

$$w(j,i')+w(p[i],i)\ge w(j,i)+w(p[i],i')$$

移项，可得

$$v(p[i],i')-w(p[i],i)\le w(j,i')-w(j,i)$$

与第一个不等式相加，可得

$$f[p[i]]+w(p[i],i')\le f[j]+w(j,i')$$

即$i'$的最优决策点一定大于等于$p[i]$。故$f$具有决策单调性。

应用

那么知道其有决策单调性后，有什么应用呢？

既然其有决策单调性，定义$p[i]$表示$i$的最优决策点，则$p$内一定是非严格单调递增的。

那么根据此性质，满足决策单调性的题目主要有两种处理手法。

方法一：单调队列

可以用单调队列维护决策集合$p$。

当求出一个新的$f[i]$时，考虑$i$可以作为哪些$f[i']\ (i'>i)$的最优决策。根据决策单调性，我们一定可以找到一个位置，在该位置之前，$p$内存储的决策都比$i$要优，其后都比$i$差。于是便可以将该位置及其后面的部分全部变为$i$，即此时它们的最优决策均为$i$。

一个位置一个位置的修改效率很低，所以可以建立一个队列，代替$p$。队列中保存三个量$(j,l,r)$，表示$p[l$~$r]$的值都是$j$。

对于每个$i\in[1,n]$，执行以下操作：

1. 检查队头：设队头为$(j_0,l_0,r_0)$，若$r_0=i-1$，则删除队头（因为队头不需要了，$f[i]$之前的值已经被求出）。否则则令$l_0=i$。

2. 取队头保存的最优决策$j$进行状态转移，计算出$f[i]$。

3. 尝试插入新决策$i$，步骤如下

   (1) 取出队尾，即为$(j_t,l_t,r_t)$

   (2) 若对于$f[l_t]$来说，$i$是比$j_t$更优的决策，即$f[i]+w(i,l_t)\le f[j_t]+w(j_t,l_t)$，记$pos=l_t$，删除队尾，返回步骤(1)。

   (3) 若对于$f[r_t]$来说，$i$是比$j_t$更优的决策，即$f[j_t]+w(j_t,r_t)\le f[i]+w(i,r_t)$，去往步骤(5)。

   (4) 否则，则在$[l_t,r_t]$上二分查找出位置$pos$，在此之前决策比$i$优，在此之后决策$i$更优，将$[l_t,r_t]$修改为$[l_t,pos-1]$，去往步骤(5)。

   (5) 把三元组$(i,pos,n)$插入队尾。

时间复杂度$O(n\ log\ n)$。

方法二：分治

假设已知$[l,r]$的最优决策在$[L,R]$上。

定义$mid=\frac{l+r}{2}$，设$dp[mid]$的最优决策为$p$，根据决策单调性，可知$[l,mid-1]$的最优决策在$[L,p]$内，$[mid+1,r]$的最优决策在$[p,R]$内。

于是将问题分割成了同类型的规模更小的问题，便可递归分治。

时间复杂度$O(n\ log\ n)$

例题 [POI2011]Lightning Conductor

给定一个长度为$n$的序列$\{a_n\}$，对于每个$i\in [1,n]$，求出一个最小的非负整数$p$，使得 $\forall j\in[1,n]$，都有$a_j\le a_i+p-\sqrt{|i-j|}$。

数据范围

$1 \le n \le 5\times 10^{5}$，$0 \le a_i \le 10^{9}$。

链接

[POI2011]Lightning Conductor

思路

$$a_j \le a_i+p-\sqrt{|i-j|},\forall j\in[1,n]$$ $$p \ge a_j+\sqrt{|i-j|}-a_i,\forall j\in[1,n]$$

而$p$为非负整数，则

$$p=\lceil \max\{ a_j+\sqrt{|i-j|}\}\rceil-a_i,\forall j\in[1,n]$$

那么问题便转变为求$\lceil \max\{ a_j+\sqrt{|i-j|}\}\rceil,\forall j\in[1,n]$。

可以考虑做两次，正做一次，将序列翻转再做一次，结果取两次的最大值，这样便可以去掉绝对值

$$\lceil \max\{ a_j+\sqrt{i-j}\}\rceil,\forall j\in[1,i)$$

定义$dp[i]=\lceil \max\{ a_j+\sqrt{i-j}\}\rceil$。

此处的$w(j,i)$即为$\sqrt{i-j}$。

定义$a+1<c$。

$$w(a,c)=\sqrt{c-a}$$ $$w(a+1,c)=\sqrt{c-a-1}$$ $$w(a,c+1)=\sqrt{c-a+1}$$ $$w(a+1,c+1)=\sqrt{c-a}$$

则

$$w(a,c+1)+w(a+1,c)-[w(a,c)+w(a+1,c+1)]=\sqrt{c-a-1}+\sqrt{c-a+1}-2\sqrt{c-a}$$

令$d=c-a$，原式变为

$$\sqrt{d-1}+\sqrt{d+1}-2\sqrt{d}=(\sqrt{d+1}-\sqrt{d})-(\sqrt{d}-\sqrt{d-1})$$

而函数$f(x)=\sqrt{x}-\sqrt{x-1}$单调递减

则该式恒小于$0$。

即$w(a,c+1)+w(a+1,c)\le w(a,c)+w(a+1,c+1)$。

可推广到对于$a\le b\le c\le d$，$w(a,d)+w(b,c) \le w(a,c)+w(b,d)$。

可以发现，这东西与四边形不等式的符号相反。将上面的证明过程符号取反（因为本题求的是$\max$），便可证明$dp$满足决策单调性。

于是采用上面两种方法实现即可。

由于函数$sqrt$较慢，且本题反复调用，可提前预处理出$\sqrt{1}$~$\sqrt{n}$。

代码（单调队列）

#include<bits/stdc++.h>
#define N 500010

using namespace std;

int n,head,tail,a[N];
double dp[N],sqr[N];
struct node{
	int l,r,p;
}q[N];

double w(int j,int i) {
	return double(a[j])+sqr[i-j];
}

int binary_search(int t,int x) {
	int ans=q[t].r+1,l=q[t].l,r=q[t].r;
	while(l<=r) {
		int mid=l+r>>1;
		if(w(q[t].p,mid)<=w(x,mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}

void insert(int i) {
	q[tail].l=max(q[tail].l,i);
	while(head<=tail&&w(i,q[tail].l)>=w(q[tail].p,q[tail].l)) tail--;
	if(head>tail) {
		q[++tail].l=i;
		q[tail].r=n;
		q[tail].p=i;
	}
	else {
		int pos=binary_search(tail,i);
		if(pos>n) return ;
		q[tail].r=pos-1;
		q[++tail].l=pos;
		q[tail].r=n;
		q[tail].p=i;
	}
}

void work() {
	head=1,tail=0;
	for(int i=1;i<=n;i++) {
		insert(i);
		if(head<=tail&&q[head].r<i) head++;
		else q[head].l=i;
		dp[i]=max(dp[i],w(q[head].p,i));
	}
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		sqr[i]=sqrt(i);
	}
	
	work();
	for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]),swap(dp[i],dp[n-i+1]);
	work();
	
	for(int i=n;i>=1;i--) cout<<(int)ceil(dp[i])-a[i]<<endl;
	
	return 0;
}

代码（分治）

#include<bits/stdc++.h>
#define N 500010

using namespace std;

int n,a[N];
double dp[N],sqr[N];

double w(int j,int i) {
	return double(a[j])+sqr[i-j];
}

void work(int l,int r,int L,int R) {
	if(l>r) return ;
	int mid=l+r>>1,p;
	double maxn=0;
	for(int i=L;i<=min(mid,R);i++) {
		if(w(i,mid)>maxn) maxn=w(i,mid),p=i;
	}
	dp[mid]=max(dp[mid],maxn);
	work(l,mid-1,L,p);
	work(mid+1,r,p,R);
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		sqr[i]=sqrt(i);
	}
	
	work(1,n,1,n);
	for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]),swap(dp[i],dp[n-i+1]);
	work(1,n,1,n);
	
	for(int i=n;i>=1;i--) cout<<(int)ceil(dp[i])-a[i]<<endl;
	
	return 0;
}

参考资料

《算法竞赛进阶指南》

【学习笔记】动态规划—各种 DP 优化