参考资料：
1.元旦集训的课件已经很好了 http://files.cnblogs.com/files/candy99/dp.pdf
2.http://www.cnblogs.com/MashiroSky/p/6009685.html
【一】
对于一类转移方程：
f[i]=max{a[i]*b[j]+c[i]+d[j]}
a[i]和c[i]是开始求解前就知道常数，b[j]和d[j]知道f[j]后就知道有关
可以使用斜率优化（不是这个形式就尽量往这个形式化）
{以下讨论不严格区分优于和不差于}
【决策单调性】：
对于两个转移j和k，设b[j]<b[k]
假设j比k优或相等，把式子一化就变成了(注意bj-bk是负数啊，我对不起小新)
-a[i]>=(d[k]-d[j])/((b[k]-b[j])
这是一个斜率的形式，记slope(j,k)=(d[k]-d[j])/((b[k]-b[j])
那么，-a[i]>=slope(j,k)时j转移比k转移优
对于一个状态就可以判断两个转移谁更优了
对于三个转移x y z ,bx<by<bz
如果slope(x,y)<=slope(y,z)，y一定不是任何一个状态的最优转移
证明：
假设y是p的最优转移，-a[p]<=slope(x,y)<=slope(y,z)，所以z比y优
然后，这不就是个上凸壳
对于f[i]=min{a[i]*b[j]+c[i]+d[j]}，只是把不等号反转而已，是一个下凸壳
【二】
如何维护这个凸壳？
以min为例
1.b单调，-a单调，凸壳只在右侧插入点且最优转移位置不断右移，单调队列/栈即可
原文：http://www.cnblogs.com/candy99/p/6258792.html