算法 动态规划 斜率优化DP

斜率优化DP

数学真**

Posted by Aspe on July 31, 2018

简介

对于形如f[i]=min(k(i)*x(j)+y(j)+b(i))[j<i]，满足k函数有单调性，的DP方程，可以运用数学推导，用单调队列，以O(n)的复杂度解决，这其实就是个板子。max同理，下面讨论min的情况

答案都是比出来的

在求f[p]时，我们来比1比i与j(i<j<p)对f[p]的贡献吧。
若i比j好，用作差法，即f[i->p]-f[j->p]<0
代入，就成了[k(p)*x(i)+y(i)+b(p)]-[k(p)*x(j)+y(j)+b(p)]<0
把式子搞的好看点-k(p)<[y(i)-y(j)]/[x(i)-x(j)]
这就是斜率了，注意除或乘负数不等式变号
这点很重要，比较i,j的优劣公式：若-k(p)<[y(i)-y(j)]/[x(i)-x(j)]，i比j优
其实在实际情况中，应该比较-k(p)*[x(i)-x(j)]>y(i])-y(j)

要开始了

单调队列！
我们要牢记，在单调队列里，1个点(x,y)是没用的，要2个点才能比较，组成斜率。
我们要想象1条队列：op[Head],op[Head+1],…op[Tail]

出队pop

斜率单调性的确定
若想使求f[p]时op[Head]队头最优，那么就满足
op[Head]比op[Head+1]优，op[Head+1]比op[Head+2]优，…，op[Tail-1]比op[Tail]优 -k(p)<[y(Head)-y(Head+1)]/[x(Head)-x(Head+1)]
[y(Head)-y(Head+1)]/[x(Head)-x(Head+1)]<[y(Head+1)-y(Head+2)]/[x(Head+1)-x(Head+2)]
…
即队列里两两组成的斜率单调递增，也就是1个凸壳 注意，k函数有单调性。 所以，当-k(p)>[y(Head)-y(Head+1)]/[x(Head)-x(Head+1)]时，弹出队头
当-k(p)<[y(Head)-y(Head+1)]/[x(Head)-x(Head+1)]时，op[Head]就是最优解

入队push

斜率的决策单调性
当想要把1个新元素i入队
若op[Tail-1]与op[Tail]的斜率为k1，op[Tail]与i的斜率是k2，如果k1>k2则可弹出op[Tail]
假设有-k(p)>[y(op[Tail-1])-y(op[Tail])]/[x(op[Tail-1])-x(op[Tail])]
即op[Tail-1]没有op[Tail]优
那么肯定有-k(p)>[y(op[Tail])-y(i)]/[x(op[Tail])-x(i)]
即op[Tail]没有i优
那么要op[Tail]有何用？
所以当k1>k2时弹出队列，队列两两的单调性就得以保障。
实际情况中，应比较Y(k1)X(k2)>Y(k2)X(k1)，交叉相乘

总结

通过数学的转换，把两个值的优劣，通过斜率展现
然后发现愉快的单调性，就解决了这个问题
注意： 1，long long
2，莫须有的位置（初始化）
3，符号与不等式的变换
4，精度

模板

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

const int ML=1000100;

int op[ML];

long long f[ML];

#define B(p) (??)
#define K(p) (??)
#define X(p) (??)
#define Y(p) (??)
#define Dx(p1,p2) (X(p1)-X(p2))
#define Dy(p1,p2) (Y(p1)-Y(p2))

int main()
{
	for (int i=1,H=0,T=1; i<=n; i++)
	{
		for ( ; H+1<T && K(i)*Dx(op[H],op[H+1])<=Dy(op[H],op[H+1]); H++); //pop
		
		int p=op[H];
		
		f[i]=K(i)*X(p)+Y(p)+B(i); //get
		
		//cout<<i<<" "<<op[H]<<" "<<f[i]<<endl;
		//for (int j=H; j<T; j++) cout<<op[j]<<" "; cout<<endl;
		
		for ( ; H+1<T && Dy(op[T-2],op[T-1])*Dx(op[T-1],i)>=Dy(op[T-1],i)*Dx(op[T-2],op[T-1]); T--); //push
		
		op[T++]=i;
	}
	
	cout<<f[n];
	
	return 0;
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：斜率优化DP”
CATALOG
    FRIENDS