斜率优化dp 学习笔记

2/22/2017来源:ASP.NET技巧人气:1199

从一个问题开始 真正理解斜率优化dp orz ISA

1 问题

Apio 2010 特别行动队

1.1 题意简述

给出一个序列x1,x2...xn,将其划分成若干个连续的区间,每一段区间[l,r]的价值为ax2+bx+c,其中x=∑i=lrxi 现在你需要最大化序列的价值

1.2 数据范围

对于20%的数据,n≤1000 对于100%的数据,1≤n≤106−5≤a≤−1|b|≤107|c|≤1071≤xi≤100

1.3 讨论

1.3.1 20pts

f(i)表示将序列的前i个划分若干段的最大价值,si表示序列的前缀和 直接根据题意,可以列出状态转移方程 f(i)=max{f(j)+a∗(si−sj)2+b∗(si−sj)+c},1≤j<i 然后直接dp就可以了 时间复杂度O(n2)

1.3.2 100pts

数据范围只能允许一个O(n)级别的算法

将转移方程进一步展开,能得到 f(i)=max{f(j)+as2i−2asisj+as2j+bsi−bsj+c},1≤j<i 将其顺序调整,写成下面的形式 f(i)=max{−2asjsi+f(j)+as2j−bsj+as2i+bsi+c},1≤j<i 观察这个式子

首先,最后三项,只和a,b,c以及si有关。换句话说,在求f(i)的值时,这三项是与j的选取无关的,我们称之为常数项 对于常数项,可以直接将其拿到max之外 f(i)=max{−2asjsi+f(j)+as2j−bsj}+as2i+bsi+c,1≤j<i

然后再观察前面4项,可以发现si是与j的选取无关的,只与si的选取有关;而其余都只与j的选取有关,而与i的选取无关 si有什么性质? si为正项序列的前缀和,显然它一定是对于1...n单调递增的 在求解f(i)的过程中,我们也一定是按照1...n的顺序求,也就是说,在求解f(i)的过程中si单调递增

我们考虑将前四项抽象成一条直线 令y=kx+b 其中k=−2asjb=as2j−bsj 也就是说,对于每一个j(1≤j≤n),都有一条确定的直线 那么在求解f(i)的时候,对于之前的一个确定的j,将si带入解析式就能求出这个j所对应的函数值 如果枚举每一个j,求出相应的函数值来更新f(i)的话,实际上就是O(n2)dp的方法了 但是我们现在不能枚举,需要直接求出,也就是说,需要确定一条能取到最优值的直线

所以说,什么是斜率优化dp? 对于每一个i(1≤i≤n),将i抽象成一条直线 求f(i)时,求之前的所有直线在自变量为某一个数时的最优值 根据直线的斜率和自变量的增减关系,维护出一个O(n)的算法 明白了这个之后,就已经基本上明白了斜率优化的大体过程

1.4 题解

对于这道题来说 由于−5≤a≤−1,可以得出k>0,即所有直线的斜率为正 由于si单增,求f(i)的过程中,顺次加入直线,直线的斜率也始终单增 维护一个斜率单增的单调双端队列,两个指针l,r

每一次加入一条直线yi之前,判断队首的两条直线ylyl+1si处的函数值,如果yl≤yl+1,说明直线yl已不是最优值,并且以后也不可能成为最优值,将其出队 计算f(i),此时最优的直线即为队首的直线yl 加入直线yi,如果yiyr−1已经将yr完全覆盖,那么将yr弹出

举个栗子 这里写图片描述 在求解f(3)的时候,需要查看f(1)f(2)所表示的两条直线在s3处的函数值,然后取最大 如图所示,显然选y2比选y1要优 由于si单增,以后在求解f(4)、f(5)...的时候,这两条直线在s4、s5...处的函数值y1也不可能比y2更优,所以y1实际上就已经可以扔掉了

还有一种情况 这里写图片描述 可以发现,顺次插入y1,y2,y3这三条直线,因为要取最大值,y2实际上已经被y1y3完全覆盖了,无论si取何值,它都已经不可能成为最优的答案,这个时候y2也可以扔掉了 实际上就是维护了一个下凸壳啊

我刚开始不明白为什么完全覆盖的要扔掉,不扔直接做不行么 这里有一个反例 这里写图片描述 此时y1y3已经将y2完全覆盖,应该扔掉 但是如果不扔掉的话,查询此时在s4处的最优值 显然y1>y2,这个时候会默认y1即为最优值,不会将y1弹出 而实际上y3才是真正的最优值 所以判断是否有两条直线将另外一条覆盖是完全必要的

如何判断两条直线已经被另一条直线覆盖? 知识储备:初中数学 如上图,令y1=k1x+b1,y2=k2x+b2,y3=k3x+b3 则求y1y3的交点横纵坐标为 k1x+b1=k3x+b3 x=b3−b1k1−k3 y=k1b3−b1k1−k3+b1 然后求y2x处的函数值 y2=k2b3−b1k1−k3+b2y2≤yk2b3−b1k1−k3+b2≤k1b3−b1k1−k3+b1 b3−b1k1−k3≤b2−b1k1−k2 (k1−k3)∗(b2−b1)≤(k1−k2)∗(b3−b1) 那么直线y2已经被y1y3完全覆盖 如果斜率为负或者斜率单减的话别搞错了正负号就好

这就是整个斜率优化的过程

1.5 代码

代码简洁清晰明了

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define LL long long #define N 1000005 int n,l,r; LL a,b,c,x; int q[N]; LL s[N],f[N]; LL K(int j) {return -2*a*s[j];} LL B(int j) {return f[j]+a*s[j]*s[j]-b*s[j];} LL Y(int i,int j) {return K(j)*s[i]+B(j);} bool cover(int x1,int x2,int x3) { LL w1=(K(x1)-K(x3))*(B(x2)-B(x1)); LL w2=(K(x1)-K(x2))*(B(x3)-B(x1)); return w1<=w2; } int main() { scanf("%d",&n); scanf("%lld%lld%lld",&a,&b,&c); for (int i=1;i<=n;++i) scanf("%lld",&x),s[i]=s[i-1]+x; l=r=0; for (int i=1;i<=n;++i) { while (l<r&&Y(i,q[l])<=Y(i,q[l+1])) ++l; f[i]=Y(i,q[l])+a*s[i]*s[i]+b*s[i]+c; while (l<r&&cover(i,q[r],q[r-1])) --r; q[++r]=i; } PRintf("%lld\n",f[n]); }

2 斜率优化dp

2.1 常见形式

斜率优化dp的状态转移方程有一些比较特殊的性质:

求解最值 每一个状态能转化成一条直线 在求解某一个状态时,因变量为求解的状态值,自变量为与这个状态相关的量 自变量满足单调性,斜率满足单调性

2.2 基本方法

将状态转移方程化成能表示成直线的形式 找出自变量、因变量、斜率、截距,讨论自变量的单调性、斜率的正负及单调性 维护单调双端队列,维护上凸/下凸壳

3 相关题目

题目难度尽量递增 ps 原来写的代码都好丑

bzoj1597 土地购买 http://blog.csdn.net/clove_unique/article/details/51244336 bzoj3156 防御准备 http://blog.csdn.net/clove_unique/article/details/51250213 bzoj3437 小P的牧场 http://blog.csdn.net/clove_unique/article/details/51297305 bzoj1010 hnoi2008 玩具装箱 http://blog.csdn.net/Clove_unique/article/details/51225398 bzoj3675 apio2014 序列分割 http://blog.csdn.net/clove_unique/article/details/51297313 bzoj1096 zjoi2007 仓库建设 http://blog.csdn.net/clove_unique/article/details/51244357 bzoj4518 sdoi2016 征途 http://blog.csdn.net/clove_unique/article/details/51224588