从一个问题开始
真正理解斜率优化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|≤107，1≤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之外
然后再观察前面4项，可以发现si是与j的选取无关的，只与
si有什么性质？
si为正项序列的前缀和，显然它一定是对于1...n单调递增的
在求解f(i)的过程中，我们也一定是按照1...n的顺序求，也就是说，在求解f(i)的过程中si单调递增
我们考虑将前四项抽象成一条直线
令y=kx+b
其中k=−2asj，b=f(j)+as2j−bsj
也就是说，对于每一个j(1≤j≤n)，都有一条确定的直线
那么在求解f(i)的时候，对于之前的一个确定的j，将
如果枚举每一个
但是我们现在不能枚举，需要直接求出，也就是说，需要确定一条能取到最优值的直线
所以说，什么是斜率优化dp？
对于每一个i(1≤i≤n)，将i抽象成一条直线
求
根据直线的斜率和自变量的增减关系，维护出一个O(n)的算法
明白了这个之后，就已经基本上明白了斜率优化的大体过程
1.4 题解
对于这道题来说
由于−5≤a≤−1，可以得出k>0，即所有直线的斜率为正
由于si单增，求f(i)的过程中，顺次加入直线，直线的斜率也始终单增
维护一个斜率单增的单调双端队列，两个指针l,r
每一次加入一条直线yi之前，判断队首的两条直线yl和yl+1在si处的函数值，如果yl≤yl+1，说明直线yl已不是最优值，并且以后也不可能成为最优值，将其出队
计算f(i)，此时最优的直线即为队首的直线yl
加入直线yi，如果yi与yr−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实际上已经被y1和y3完全覆盖了，无论si取何值，它都已经不可能成为最优的答案，这个时候y2也可以扔掉了
实际上就是维护了一个下凸壳啊
我刚开始不明白为什么完全覆盖的要扔掉，不扔直接做不行么
这里有一个反例
此时y1和y3已经将y2完全覆盖，应该扔掉
但是如果不扔掉的话，查询此时在s4处的最优值
显然y1>y2，这个时候会默认y1即为最优值，不会将y1弹出
而实际上y3才是真正的最优值
所以判断是否有两条直线将另外一条覆盖是完全必要的
如何判断两条直线已经被另一条直线覆盖？
知识储备：初中数学
如上图，令y1=k1x+b1,y2=k2x+b2,y3=k3x+b3
则求y1与y3的交点横纵坐标为
k1x+b1=k3x+b3
x=b3−b1k1−k3
y=k1b3−b1k1−k3+b1
然后求y2在x处的函数值
若y2≤y
即k2b3−b1k1−k3+b2≤k1b3−b1k1−k3+b1
b3−b1k1−k3≤b2−b1k1−k2
(k1−k3)∗(b2−b1)≤(k1−k2)∗(b3−b1)
那么直线y2已经被y1和y3完全覆盖
如果斜率为负或者斜率单减的话别搞错了正负号就好
这就是整个斜率优化的过程
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