[BZOJ3672/Luogu2305][NOI2014]购票(点分治,动态规划,斜率优化)

发布于 2018-04-08  13 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3672/Luogu2305][NOI2014]购票(点分治,动态规划,斜率优化)

Description

今年夏天,NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发,到SZ市参加这次盛会。
全国的城市构成了一棵以SZ市为根的有根树,每个城市与它的父亲用道路连接。为了方便起见,我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v,我们给出了它在这棵树上的父亲城市 fv 以及到父亲城市道路的长度 sv。
从城市 v 前往SZ市的方法为:选择城市 v 的一个祖先 a,支付购票的费用,乘坐交通工具到达 a。再选择城市 a 的一个祖先 b,支付费用并到达 b。以此类推,直至到达SZ市。
对于任意一个城市 v,我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a,只有当它们之间所有道路的总长度不超过 lv 时,从城市 v 才可以通过一次购票到达城市 a,否则不能通过一次购票到达。对于每个城市 v,我们还会给出两个非负整数 pv,qv 作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d,那么从城市 v 到城市 a 购买的票价为 dpv+qv。
每个城市的OIer都希望自己到达SZ市时,用于购票的总资金最少。你的任务就是,告诉每个城市的OIer他们所花的最少资金是多少。

Tag

点分治,动态规划,斜率优化

解决思路

设F[i]表示i这一点到达根的最优值,那么对于每一个合法的j有,其中Depth[i]表示i这一点到根的距离
\[F[i]=min(F[j]+(Depth[i]-Depth[j])*P[i]+Q[i])\]
但关键就是这个合法的j不好确定。就算没有距离的限制,要想在树上动态维护一个凸包?可持久化凸包?再加上个距离的限制,完全不能解。
考虑另一种方法。假设对于一个点i,我们已经能够确定i以及i到根路径上所有的点的答案,那么如何用这些答案取更新i的子树内的点的答案呢?
考虑把i子树内的点按照它的深度-距离限制排序,这样就可以得到一个单调的序列。同时,我们从i开始跳i的父亲,每一次把符合当前限制的点加入凸包,这样我们就可以用i到根路径上的点的权值来更新i子树内的点了。
那么,如何选择这个点i呢?为了保证复杂度,可以用点分治来解决。每一次点分治重心,先递归处理重心到当前真正的根,得到这一条路径上的答案,这样才能用来更新重心的子树。

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3672/Luogu2305][NOI2014]购票(点分治,动态规划,斜率优化)


HNCJ OIer 一枚