换几种称呼:斜率凸优化 带权二分 这几个本质上其实并没有什么区别呢.
解决问题的范畴
给一个选物品的限制条件,在 $N$ 个物品里要求恰好选 $K$ 个,让你最大化/最小化权值.
且当选择物品的数量越多的时候权值越大/越小.
分析
普通的DP可以在$O(nk*C)$的时间内解决这个问题,其中 $C$ 是转移的复杂度.
但是要是碰上独留的出题人呢.
这个 $K$ 的限制十分的令人头大, 不如不考虑这个玩意.也就是去掉物品个数限制 $K$ .
我们令取一个物品的附加权值为 $Cost$
那么根据解决问题的范畴里面的性质.
假设我们 $Cost$ 越大 我们选择的物品个数随之减少/增大, 权值也随之减少/增大
那么我们在转移 $DP$ 的时候可以考虑记录下取物品的个数
根据是否大于 $K$ 来调整权值.
最后拿答案减掉 $Cost$ 的影响就是答案.
这样的复杂度将 $K$ 这一维缩成了 $logCost$.对于 $K$ 比较小的来说 可能优化效果并不明显.
算是个黑科技吧 今天也是偶尔遇到了才学了学呢
栗子
见新的post吧.