1D/1D动态规划优化学习笔记

声明

原文传送门
阅读请注意，编写原文时本人尚年轻，因此原文有数处错误且难以理解，请读者加以注意。
一直不准备补的这个坑，我终于回来补了。
原来只是单纯介绍斜率优化，现在把类似的优化一并总结了。

1D/1D动态规划

所谓1D/1D动态规划，指的是状态数为$O(n)$，每一个状态决策量为$O(n)$的动态规划方程，直接求解的时间复杂度是$O(n^2)$。但是，绝大多数的方程通过合理的组织与优化都是可以直接优化到$O(n\log n)$乃至$O(n)$的时间复杂度的。
优化方法包括：

• 单调队列优化至$O(n)$
• 斜率优化至$O(n\log n)$或$O(n)$
• 决策单调性优化至$O(n\log n)$

接下来我们一一介绍。

单调队列

算法简介

单调队列优化Dp问题是最简单最基础的一类优化方法，新学者们会很容易理解其优化原理。

特征方程：$f(x)=\min\limits_{k=b[x]}^{x-1}\{g(k)+w[x]\}$，其中$b[x]$随$x$不降

本方程的最小化$\min$亦可为最大化$\max$，若为最大化$\max$，后述不等符号均需改变，本文均以最小化$\min$举例。
方程中，$b[x]$是$x$状态的转移起始来源，即转移来源区间是$[b[x],x-1]$，$b[x]$需要满足不降的特征。
若满足此特征方程，则可以利用单调队列优化Dp过程，将Dp复杂度降至$O(n)$。

优化原理

注意到：如果有$i$状态有两个转移来源$j,k$，其中$j\le k$而$g(k)\le g(j)$，则决策$j$是毫无用处的，因为$b[x]$单调，如果$j$可以作为合法决策，那么$k$一定可以作为合法决策，又因为$g(k)$比$g(j)$更小，因此可以认为$k$比$j$更优，那么我们便可以舍去决策$j$。
因此我们维护一个单调队列，保证决策下标$k$升序排列，那么可以注意到，在单调队列中$g(k)$同样是不降的。

优化过程

我们使用一个单调队列来维护决策表，对于每一个状态$f(x)$，计算过程如下：

1. 队首元素持续出队，知道队首元素在区间$[b[x],x-1]$中。
2. 此时队首元素$k$即为$f(x)$的最优决策。
3. 计算$g(x)$，将其插入单调队列的尾部，同时维护队列的单调性（将队尾与$x$不满足单调性的决策全部出队）

重复执行以上步骤直到所有$f(x)$计算完成。

时间复杂度

由于每一个元素只被计算了一次，并且每一个元素只入队了一次，因此时间复杂度均摊为$O(n)$。

例题及应用

例题一.滑动窗口

    给你一个长度为$N$的数组，一个长为$K$的滑动的窗体从最左移至最右端，你只能见到窗口的$K$个数，每次窗体向右移动一位，如下图：

    你的任务是找出窗体在各位置时的最大值和最小值。

这是一道模板题，状态转移方程是$f(x)=\min\limits_{j=x-k+1}^{x-1}\{a[j]\}$，核心代码如下：

n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
deque<int>Min;
for(int i=1; i<=n; i++) {
	while(!Min.empty()&&Min.front()<=i-m)Min.pop_front(); //维护队首 
	ans1[i]=a[Min.front()];
	while(!Min.empty()&&a[Min.back()]>=a[i])Min.pop_back(); //维护队尾 
	Min.push_back(i);
}
for(int i=m; i<=n; i++)printf("%d ",ans1[i]);
putchar('\n');
deque<int>Max;
for(int i=1; i<=n; i++) {
	while(!Max.empty()&&Max.front()<=i-m)Max.pop_front(); //维护队首 
	ans2[i]=a[Max.front()]; 
	while(!Max.empty()&&a[Max.back()]<=a[i])Max.pop_back(); //维护队尾 
	Max.push_back(i);
}
for(int i=m; i<=n; i++)printf("%d ",ans2[i]);

例题二.「bsoj3425」分班

传送门

应用三.优化背包问题

传送门

斜率优化

算法简介

斜率优化Dp问题入门会较为困难，因为这大概是在学习过程中OI选手第一次遇到与数学内容结合的算法。
但斜率优化反而是一个重要的知识点，它简单地将1D/1D动态规划优化至$O(n)$，同时斜率优化也有更困难的延申与拓展。
其中最简单的斜率优化形式还是单调队列，但优化原理大不相同。

特征方程：$f(i)=\min\limits_{j=1}^{i-1}\{a[i]\times x(j)+b[i]\times y(j)\}$

其中，$x(j),y(j)$都是可以在常数时间内通过$f(j)$唯一决定的二元组。
这个特征方程涵盖的范围很广，但能够使用斜率优化的状态转移方程都可以转化成以上形式。

优化原理与过程

对于一个决策$j$进行考虑，即将考虑的转移是：$f(i)=a[i]\times x(j)+b[i]\times y(j)$。
我们使用线性规划进行转化（线性规划大概会在高二学习），我们以$x(j)$为横轴，$y(j)$为纵轴建立平面直角坐标系，这样决策$j$就可以用坐标系上的一个点表示。
原方程可以转化为$f(i)=\min\{a[i]\times x+b[i]\times y\}$，这类似一个直线的一般式方程，我们将其转化为斜截式方程：$y=-\frac abx+\frac{f(i)}b$，假设$b\gt0$，则目标是最小化直线的纵截距。
我们用一个斜率为$-\frac ab$的直线从负无穷向上平移，所碰到的第一个点即为最优决策$j$，利用这个点我们可以计算出最优的$f(i)$。

不难发现，所有可能的最优决策点必定在平面点集的凸包上，换句话说不在凸包上的点一定不是最优决策点。
当$b\gt0$时，我们需要维护一个右下凸包或左上凸包（根据点集的特征决定）。
那么现在我们的任务转化为了维护凸包。
根据直线斜率和数据点分布的特征，我们可以分为三种情况。

1.决策直线的斜率与二元组的横坐标同时满足单调性

这种情况的处理非常简单，因为斜率变化是单调的，因此决策点必然在凸壳上单调移动，我们只需要维护一个单调队列和一个决策指针即可。
对于每一个状态$f(i)$，计算过程如下：

1. 决策指针（队首）后移，直到最佳决策点$j$。
2. 进行决策并计算$f(i)$。
3. 计算$x(i),y(i)$，将二元组加入队尾，同时更新凸壳（如图）。
   

时间复杂度$O(n)$

2.二元组的横坐标满足单调性

我们使用同样的方式维护凸壳，在查询最优决策点的时候，使用二分查找找到最接近的斜率。

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

3.不满足任何限制

虽然决策点仍然在凸壳上，但是在维护凸壳时就有大麻烦了。我们需要一一验证凸性，接着需要拼接凸壳，最坏的时间复杂度$O(n)$，这相当于根本没有优化！
该怎么做呢？分为两种情况：

1. 允许离线：此时我们可以使用cdq分治来较为简单地解决这个问题，时间复杂度为$O(n\log n)$。
2. 强制在线：此时我们只能使用平衡树来维护凸包了，我们以横坐标为关键字建立平衡树，查找和插入的过程均为$O(n\log n)$，在维护凸壳时，先将新数据点Splay到根结点，剩下的结点必定分居左子树与右子树。然后我们以左子树为例，后序遍历依次查找结点，直到找到一个满足凸性的结点，将这个结点Splay到根结点的左儿子，然后我们删掉这个结点的右子树即可，时间复杂度为$O(n\log n)$，但实现起来非常复杂。

例题集

• 「hdu3507」打印文章（贴的是别人的博客，不要看以前我写的分析）
• 「HNOI2008」玩具装箱
• 「CEOI2004」锯木厂选址
• 「ZJOI2007」仓库建设
• 「USACO 2008 March Gold」土地购买
• 「APIO2010」特别行动队
• 「APIO2014」序列分割
• 「bzoj3437」小P的牧场
• 「SDOI2016」征途

决策单调性

算法简介

决策单调性可以理解为四边形不等式优化Dp的1D/1D版本。
可以利用决策单调性优化的动态规划的特点是：其决策的下标单调。

特征方程：$f(x)=\min\limits_{i=1}^{x-1}\{f(i)+w[i,x]\}$

已知结论

如果用$k(x)$表示状态$x$取到最优值的决策，则决策单调性表述为：
$\forall i\le j,k(i)\le k(j)$当且仅当：$\forall i\le j,w[i,j]+w[i-1,j-1]\le w[i-1,j]+w[i,j-1]$。
因此满足转移代价四边形不等式，则可以利用决策单调性进行优化。
但是转移的代价是否满足四边形不等式，并非一个很容易判断的问题，因此推荐的姿势是：
在确认动态规划需要优化且不满足以上两种方式时，打表验证决策点是否单调。

我以前的笔记似乎记录了一种较为方便的判断决策单调性是否成立的方法，这里需要等我找到笔记后来填坑。

（update 2019/07/30：找到笔记了）
记$G(x,i)$为状态$x$根据转移方程$f(x)$使用$i$决策转移的结果。
设决策点$i\lt j$，决策$j$比$i$更优（假设问题要求最小化），则$G(x,i)\ge G(x,j)$
将不等式解出后我们可以得到决策$j$比$i$更优的条件。

1. 若条件仅有单向限制（另一端为无穷）且不等号不会变向（单调性），则满足决策单调性。
2. 若无解，则满足决策单调性。（决策$j$无用）
3. 若条件是一段区间（双边限制），则不满足决策单调性。

优化过程

如何实现决策单调性呢？我们可以在枚举决策的时候，不从1开始，而是从$k(x-1)$开始，但这样只能减少常数，并不能降低时间复杂度。
另一种想法时从$k(x-1)$开始枚举决策更新$f(x)$，一旦发现决策$j$比决策$j+1$更优，就停止决策过程，选择决策$j$作为$f(x)$的最优决策。但这样是错误的，因为决策单调性并没有保证$f(j)+w[j,x]$有什么好的性质。

如果我们换一个角度，思考对于一个已经计算出的状态$f(j)$，它能够更新哪些状态？这样，每一步过程中的某些决策可能不是最优的，但是当算法结束时所有状态的决策一定是最优的。
一开始，只有$f(1)$的函数值被计算出，所以所有状态的当前最优决策点都是1。
决策表：1111111111111111111111111111111111111111111
现在由于$f(2)$的值已经确定了，$f(2)$的最优决策只能是$1$，那么我们使用决策$2$来更新这个决策表。由于决策单调性，新的决策表只能是下面这种形式：
决策表：1111111111111222222222222222222222222222222
因此我们可以使用二分法来寻找1与2之间的转折点，因为如果在一个点$x$上，决策$2$更好，所有比$x$大的状态都是决策$2$更好；如果$x$上决策$1$更好，则所有比$x$小的状态都是决策$1$更好。
当决策表更新完毕后，$f(3)$即可确定，现在用3更新所有状态，新的决策表只能有以下两种形式：
决策表：1111111111111222222222222222222233333333333
决策表：1111111111333333333333333333333333333333333

此时我们可以设计出整个算法流程：
使用一个栈维护数据，栈中的每一个元素保存一个决策可更新区间的起始位置与结束位置，这些区间肯定相互连接且依次递增。当插入一个新的决策时，从栈顶往栈底扫描栈，依次考察栈顶决策：

1. 如果新决策$i$比栈顶的决策$top$对于$top$起始位置更优，则弹栈，全部抛弃栈顶决策$top$，将区间继承给新决策$i$，继续扫描下一个栈顶决策。
2. 如果栈顶决策$top$对于其起始位置更优，则转折点必定在$top$所能更新的区间中，二分查找转折点，然后将新决策$i$入栈，结束更新操作。

时间复杂度

由于一个决策只会入栈一次，均摊时间为$O(1)$，但是由于二分查找的存在，时间复杂度为$O(n\log n)$。

例题

例题一.「BZOJ2216」Lightning Conductor

    已知一个长度为$n$的序列$a_1,a_2,\ldots,a_n$。
    对于每个$1\le i\le n$，找到最小的非负整数$p$满足对于任意的$j$，$a_j\le a_i+p-\sqrt{\mid i-j\mid}$。

模板题，满足决策单调性。
需要注意的是，决策单调性的代码比较严格，交换顺序或者细节更改可能会直接导致错误。

struct QueNode {
	int pos,l,r; //pos决策点的贡献是区间[l,r] 
	QueNode(int p=0,int _l=0,int _r=0):pos(p),l(_l),r(_r) {}
};

const int maxn=1000005;
int n;
double a[maxn],f[maxn],g[maxn];

double Cal(int x,int y) {
	return a[y]+sqrt(x-y);
}

int Binary(int Left,int Right,int x,int y) {
	while(Left<=Right) {
		int mid=(Left+Right)>>1;
		if(Cal(mid,x)>Cal(mid,y))Right=mid-1;
		else Left=mid+1;
	}
	return Left;
}

void Dp(double* ans) {
	deque<QueNode>Q;
	Q.push_back(QueNode(1,1,n));
	for(int i=1; i<=n; i++) {
		while(!Q.empty()&&Q.front().r<i)Q.pop_front();
		if(!Q.empty())ans[i]=Cal(i,Q.front().pos);
		while(!Q.empty()&&Cal(Q.back().l,i)>Cal(Q.back().l,Q.back().pos))Q.pop_back(); //决策top被吃掉了
		if(Q.empty()) {
			if(i+1<=n)Q.push_back(QueNode(i,i+1,n));
		} else {
			int pos=Binary(Q.back().l,Q.back().r,i,Q.back().pos);
			if(pos>Q.back().r)continue;
			Q.back().r=pos;
			if(pos+1<=n)Q.push_back(QueNode(i,pos+1,n));
		}
	}
}

int main() {
	n=Get_Int();
	for(int i=1; i<=n; i++)a[i]=Get_Int();
	Dp(f);
	reverse(a+1,a+n+1);
	Dp(g);
	reverse(a+1,a+n+1);
	reverse(g+1,g+n+1);
	for(int i=1; i<=n; i++)printf("%d\n",max(0,(int)ceil(max(f[i],g[i])-a[i])));
	return 0;
}

例题二.「NOI2009」诗人小G

埋坑。

例题三.「NOI模拟赛3.13」珠宝jewelry

传送门

总结

虽然本文介绍的是1D/1D动态规划，但其实可以将nD/mD动态规划将以转化并使用以上技巧进行优化降低时间复杂度。
Dp是一类难度较大的问题，考察选手全面的思维能力，对于初学者来说相当困难。如何提升Dp能力呢？除了多做题也没有什么更好的方法。
每做一道Dp的题目，都应该思考其是否能够优化，或者能否对题目加以改变之后进行优化，这对于提升选手的能力也有很大的帮助。
希望本文能够帮到各位读者，谢谢。

参考资料

• 1D1D动态规划优化初步
• 斜率优化Dp详解
• Dp优化笔记手稿 by Bill_Yang