RainAir
My OI Blog
RainAir
「八省联考2018」林克卡特树

主要是为了学习一波 wqs 二分。

首先发现这个题目等价于把树切成 k+1 块 每块内选个直径加起来,也就等价于在树上找 $k+1$ 条不相交的链使得收益最大。

考虑树上每一条链都可以拆成两条深度单调的链,所以我们可以设 $f[i][j][0/1/2]$ 表示现在在 $i$ 点 已经选择了 $j$ 个链 当前 $i$ 点的状态是(没有链经过/有一条单链待匹配/有链经过),转移一下就可以了,复杂度 $O(n^2)$

对于这一类“恰好选 $k$ 个” 的问题,如果优化不掉 $k$ 这一维,就可以考虑 wqs 二分。

我们设 $f(x)$ 表示选 $x$ 个的最优值,首先发现 $f$ 是凸的(导函数单调),也就是平面上若干个点 $(x,f(x))$ 构成了一个凸壳。上面的暴力 dp 就是求出凸包上所有点的过程,但我们实际上只想求出题目要求的点 $(x_0,f(x_0))$。我们考虑我们二分一条斜率固定的直线 $k$ 去切这个凸包。这个时候这条直线切到的点 $(x,f(x))$ 满足 $f(x) = kx+C$,回忆凸壳的定义我们发现 $C=f(x)-kx$ 应当取最大值,我们求出 $C$ 在什么时候取到最大值就可以求出 $x$,然后根据导函数的单调性来决定斜率的增减。这里求最大值可以看成每个物品有额外的代价/收益,然后扔掉数量的限制去 dp 最大收益的数量。

但是这样会有一个问题:让 C 取最大值的点可能是不唯一的,也就是我们二分最后得到的结果不一定是一个点,而是一条直线上的许多点。这时候我们观察 $f(x)=kx+C$ 发现 $C,k$ 都是固定的,我们只需要让 $x$ 尽量大就可以取到最大值了。(根据题目会不同)

总结做题思路:优化不下去$\to$ 暴力 dp 打表看差分表 $\to$ 发现凸函数,用 wqs 二分。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/978
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「八省联考2018」林克卡特树
主要是为了学习一波 wqs 二分。 首先发现这个题目等价于把树切成 k+1 块 每块内选个直径加起来,也就等价于在树上找 $k+1$ 条不相交的链使得收益最大。 考虑树上每一条链都可以拆成两条…
扫描二维码继续阅读
2020-02-08
标签
近期评论