【BZOJ3672】【NOI2014】购票

我弃疗好吗。。

首先\(dp_i=min(dp_j+p_i(dis_i-dis_j))+q_i\)

首先如果它是一条链的话可以维护一个凸包在上面二分

但是树怎么办呢。。可以考虑分治

每次处理被更新点在重心以下,决策点在重心以上的部分。也就是处理跨过这个点的决策路线。

这样我们可以对下面的点进行排序,依次更新并加入可用的祖先,上面的部分建凸包。

说点什么

您将是第一位评论人!

提醒
wpDiscuz