almost 4 years ago

把式子写成y=kx+b的形式

其中,b是要求的值通常记为f[x],是要最大化或最小化的

k是与i有关的.

x,y是与j有关的.

大体分为四类:

1.x与k同时单调,正常单调队列维护,决策时在队首不断弹,加点时队尾graham式维护。
2.x单调,k不单调,正常graham式维护凸壳,决策时在凸壳上三分。还是二分?
3.x不单调,k单调,平衡树维护凸壳,每次决策后可以删掉一些点。
4.x不单调,k不单调,平衡树维护,正常决策,不能删点。
关于平衡树维护(摘自1D1D动态规划优化初步)
http://lavender1010.blog.com/2014/04/28/little-of-%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96/
动态凸包一定要写写写写!!!!

← 【poj2728】【最优比例生成树】DESERT KING 【bzoj2553】【ac自动机】【dp】【矩阵优化】禁忌 →
 
comments powered by Disqus