斜率优化

突然想学一下斜率优化，翻了一下课件和Accept的博客才发现内涵丰富。

结果是个坑，坑了我两天。

斜率优化是一种DP优化：

对于形如D[i]=min(j<i){D[j]+(a[i]-a[j])^2}（a[i]单调递增）

对于D[i]的决策k、j（k<j<i），D[i]决策j优于决策k即：D[j]+(a[i]-a[j])^2<D[k]+(a[i]-a[k])^2。

整理得a[i]>(D[j]-D[k]+a[j]^2-a[k]^2)/2*(a[j]-a[k])。

然后将D[i]+a[i]^2看做是yi，将2*a[i]定为xi，则上式化为(yj-yk)/(xj-xk)<a[i]，于是叫做斜率优化。

此时观察动态转移方程，就是D[i]=min{yj-xj*a[i]}+a[i]^2。

令g[j][k]=(yj-yk)/(xj-xk)，那么如果对于k<j<i，如果g[i][j]<g[j][k]，那么j不可能是最优决策。

再分两种情况证明：如果g[i][j]<a[i]，那么i决策优于j；否则如果g[i][j]>=a[i]，那么g[j][k]>=a[i]，k决策优于决策j。

于是实现起来就只要维护一个队列b1,b2,b3, ..., bm，队列中的元素对于所有k<j<i都有g[i][j]>=g[j][k]，即单调递减。

每次将元素i插入队列中时，如果g[i][b[m]]<g[b[m]][b[m-1]]，则说明b[m]点不可能是最优值，在原队列中删去b[m]，继续操作，直到满足g[i][b[m]]>=g[b[m]][b[m-1]]或队列剩下不足2个点。

求解D[i]时，如果g[2][1]<a[i]，则b[2]优于b[1]，而a[i]单调递增，则对于大于此的i，g[2][1]<a[i]恒成立，则将b[1]删除，m--。

重复操作至条件不成立或只剩下一个元素，此时对于每个1<=k<j<=m，都有g[b[j]][b[k]]>=a[i]，于是b[1]即是最优解。