【一】
对于一类转移方程：
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]}，只是把不等号反转而已，-a[i]<=slope(j,k)时j转移比k转移优,是一个下凸壳
上下凸壳不是绝对的，有时候有迷之负数
图形化的考虑，那很像直线方程对吧
斜率形式+j的常数项是y，*j的常数项是x
−a[i]∗b[j]+f[i]=c[j]+d[i]
【二】
如何维护这个凸壳？
以min为例，最优转移就是求第一点j，slope(j-1,j)<=-a,slope(j,j+1)>=-a,也就是斜率为-a的直线与这个凸壳的切点
1.b单调，-a单调，单调队列
- 插入前判断队首是不是最优转移，不是弹出队首
- 凸壳只在一侧插入点且最优转移位置不断单向移动，插入时维护凸壳弹队尾
2.b单调，-a不单调，队首不能弹，
3.
4.