看网上的斜率优化都比较玄。。。
gerw给出了一种比较好的理解方式
简单的有两种形式
一、形如 dp(i) = min / max {f(j) + g(i) * h(j) + c(i)} (j < i) //h() 一般是有单调性的
显然c(i)是可以拿出来的，就变成了
dp(i) = min / max {f(j) + g(i) * h(j)} + c(i)
g(i)对于一个i来说是定值，不妨设为k
则优化目标设为z = f(j) + k * h(j)
每个点j在二维平面上对应一个点(h(j), f(j))
则z = y + kx
即y = -kx + z
则问题转化为给出平面上一些点，求直线斜率为-k的经过这些点的直线中y轴截距最大/最小的点，显然分情况维护上凸壳或者下凸壳，由于h()单调，维护一个栈就行了，要是无序，拿平衡树就行了
另外如果g(i)单调只用维护一个单调队列，O(n)即可，否则需要二分或三分。
二、给定一个点与之前的一些点，求过这个点和之前某个点的所有直线中，斜率最大/最小的直线
情况差不多，根据单调性维护上凸壳或者下凸壳
原文：http://www.cnblogs.com/showson/p/5090682.html