关于WQS二分的一点理解

最近才学习了WQS二分,发现这是一个很有用的东西。

大概是这样一类问题:决策\(i\)对答案有\(w_i\)贡献,求恰好做\(k\)次该类决策的最大答案

考虑不限制决策的次数,但每个决策除贡献外,都减去一个代价\(cost\)

这样通过调整\(cost\)的值,就能够控制决策的次数

WQS二分其实就是二分这个\(cost\),使得最优解做不大于\(k\)次该类决策,且\(cost\)尽量大

设最优解做了\(x\)次该决策,定义\(g(x)\)为最优解(不减\(cost\)),\(f(x)\)为最优解

则有:\(g(x)=kx+f(x)\)

\(k\)其实就是\(cost\)

你会发现这其实就是在二分\(g(x)\)的斜率,使该斜率对应的\(x\)满足题意

这样我们就得到了WQS二分的条件:原贡献关于决策次数的函数\(g(x)\)斜率单调(\(g'(x)\)单调)

值得注意的是,最后得到的\(cost\),对应决策次数不一定是\(k\)\(g‘(x)\)某段水平)

但这并不影响答案,因为\(g'(x)=g'(k)\)意味着\(f(x)=f(k)\),我们要的就是\(f(k)\)

推荐题目:BZOJ2654 tree、Codeforces 739E Gosha is hunting