Bakser's Blog

我是逗比。

斜率优化的四种情况

| Comments

1.x与k同时单调,正常单调队列维护,决策时在队首不断弹,加点时队尾graham式维护。
2.x单调,k不单调,正常graham式维护凸壳,决策时在凸壳上三分。
3.x不单调,k单调,平衡树维护凸壳,每次决策后可以删掉一些点。
4.x不单调,k不单调,平衡树维护,正常决策,不能删点。
关于平衡树维护(摘自1D1D动态规划优化初步)

Comments

comments powered by Disqus