决策单调性优化DP学习笔记
HoshiuZ
·
·
题解
设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的最优决策点。
$$
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|}。
数据范围
### 链接
[[POI2011]Lightning Conductor](https://www.luogu.com.cn/problem/P3515)
### 思路
$$
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}$。
### 代码（单调队列）
```cpp
#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;
}
```
### 代码（分治）
```cpp
#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 优化](https://www.cnblogs.com/Xing-Ling/p/11317315.html)