斜率优化复习小结
这篇基本上还是自己看的，写一些碎片和注意事项
斜率优化：
①形如 DP[i]=min/max{DP[j]+A[j]+B[j]*C[i]+D[i]+E}方程，将转移方程化为 (DP[j]+A[j])=(-C[i])*(B[j])+(DP[i]-D[i]-E)
即方程斜率式:y=kx+b,其中k=-C[i]
要求C[i]单调！(斜率单调)
易证明用单调队列维护一个上凸或下凸(最直观的证明方法大概是线性规划，用代数方法亦可)，即可在线性时间求解
②形如 DP[i]=min/max{(B[i]-A[j])/(i-j)},ans=min/max（与前面一致）{DP[i]}
易证用单调队列维护一个凸结构即可
注意事项：
①比较斜率的时候是否加等号(不影响DP值，但影响转移点选取)
②先入队还是先更新DP值
③long longintdouble
④状态转移方程不要写错(虽然是废话)
练习题:
HDU 3507
UVALive 4726
CodeForces 674C
HDU 5956（树形DP，事实上暴力斜率优化可以被卡到n2，但oj上能过，如果加一个二分可以优化成nlogn，但据说在oj的数据上跑得会更慢——不过随机数据使用二分应该的确更慢一些）