[学习笔记]凸优化/WQS二分/带权二分

2019/02/20 17:35
阅读数 11

从一个题带入:[八省联考2018]林克卡特树lct——WQS二分

比较详细的:

题解 P4383 【[八省联考2018]林克卡特树lct】

 

简单总结和补充:

条件

凸函数,限制

方法:

二分斜率,找切点横纵坐标,判断k的位置

找切点坐标:

集体-mid*x(证明还是凸函数:f(x+2)-f(x+1)<=f(x+1)-f(x))仍然成立)

每次选择物品有额外代价,

找此时高点就是原凸包切点

 

为了避免凸包上多点共线并且线的横坐标区域包含k,从而使得不会二分到k,

我们ans不记录符合条件切点的纵坐标,而是记录下来符合切点坐标(大于等于/小于等于)k的(最大/最小)斜率。(因题而异)

最后把斜率带进去求出纵坐标,然后向上平移ans*k即可

进阶:

k是一个区间[l,r]也可以做

法一:求出最高点选择的最大值最小值,根据斜率再调整

法二:求出l位置的切点斜率k1,r位置的切点斜率k2,如果k1,k2异号,k=0的切点就是最优位置,否则,绝对值更小的k的l或者r就是最优解位置

 

感悟

利用凸函数上二分,再转化为求“任意选择”全局最优解,使得摆脱了k的限制,使得DP维数降低,O(n^2)-O(nlogn)

 

展开阅读全文
wqs
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部