其实是做bzoj3437时注意到的。。。这个斜率优化很显然吧。。然后发现某进队爷的做法：http://cxjyxx.me/?p=641 卧槽怎么这么复杂。。。。
其实斜率优化本来是很简单的东西><，但不知道为啥网上的推法都是各种推式子【对于有公式恐惧症的我自然是压力山大。。。
考虑这样的问题，给出一堆直线，询问x=x0时，y能达到的最大值或最小值。
这个问题显然维护凸壳就好了吧，然后在凸壳上二分。。。
如果询问是递增的，就不用二分了，直接扫就好。。
如果插入的直线k是单调的，单调栈就好了，否则直接cdq分治或平衡树维护。。。
以bzoj3437为例
sum[i]表示1~i之间b[i]的和，ssum[i]表示1~i之间b[i]*i的和。
O(N^2)的转移方程为：f[i]=min(f[j]+(sum[i]-sum[j])*i-ssum[i]+ssum[j]+a[i])
注意只与i有关的项显然可以无视之
于是我们要最小化i*(-sum[j])+f[j]+ssum[j]
把-sum[j]看成k，ssum[j]+f[j]看成b，转化为上面问题。。
然后就没了。。。所有斜率优化dp的统用方法都是这样。。
【话说写这么sb的东西会不会被人鄙视T_T
其实这玩意啊应该也有挺多人发现的。。
比如我发现了这个：http://timeplayer.blog.163.com/blog/static/20371825420155179358509