[CEOI2017]Building Bridges

[CEOI2017]Building Bridges

时间限制:1000MS      内存限制:131072KB

难度: \(7.2\)

  • 题目描述

有 \(n\) 根柱子依次排列,每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\) 。

现在想要建造若干座桥,如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间,那么需要 \((h_i-h_j)^2\) 的代价。
在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)​,注意 \(w_i\) 不一定非负,因为可能政府希望拆除某些柱子。

现在政府想要知道,通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个空格隔开的整数,依次表示 \(h_1, h_2, \cdots, h_n\) 。

第三行 \(n\) 个空格隔开的整数,依次表示 \(w_1, w_2, \cdots, w_n\) 。

  • 输出格式

输出一行一个整数表示最小代价,注意最小代价不一定是正数。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(30\%\) 的数据,有 \(1 \leq n \leq 1000\) ;

对于另外 \(40\%\) 的数据,有 \(\left| w_i \right| \leq 20\) ,保证存在一种最优方案,除了头尾两根柱子外,最多只保留两根柱子;

对于 \(100\%\) 的数据,有 \(2 \leq n \leq 10^5\),\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。

数据来源 LOJ 2483

 

 

已搬至 YZOJ P4254 。


 

 

 

按照惯例,设 \(f_i\) 为做到第 \(i\) 根柱子时的最小代价。计 \(sumw\) 为 \(w\) 的前缀和。

轻松得到转移方程 \(f_i=\min\limits_{j=1}^{i-1}\{f_j+sumw_{i-1}-sumw_j+(h_i-h_j)^2\}\) ,这样就有了 \(30pts\) 。

 

不难发现其实这是一个斜率优化的经典模型。对这个转移方程进行一些处理

\(\begin{align} f_i&=f_j+sumw_{i-1}-sumw_j+(h_i-h_j)^2 \\ \underbrace{f_i}_{b_i}&=\underbrace{f_j-sumw_j+h^2_j}_{y_j}-\underbrace{h_i}_{k_i} \cdot \underbrace{2h_j}_{x_j}+\underbrace{sumw_{i-1}+h^2_i}_{const_i} \end{align}\)

但是问题来了,这里的 \(k_i\) 和 \(x_j\) 都不是单调的。哦豁,完蛋,要写 Splay 维护下凸壳了。这个时候就要用到一种神奇的分治算法 —— CDQ分治

回顾一下斜率优化的写法:把可以实现把一个点加入单调队列的操作是因为加入的 \(x\) 是单调的,可以取队头元素为最小值是因为询问的 \(k\) 是单调的。CDQ 分治就是牢牢抓住这两点进行操作的。

因为是分治,所以要有一个分治区间 \([l, r]\) 表示用 \([l, mid]\) 中所有点的信息去更新 \((mid, r]\) 的最小值。那么如何快速做到这个更新操作呢???很简单,只需要把 \([l, mid]\) 中的点按照 \(x\) 排序,\((mid, r]\) 中的元素按照斜率 \(k\) 排序,这样就可以按照最简单斜率优化的写法去更新了。

直接在里面 std::sort()  复杂度会多个 \(log\)(虽然对于数据水的本题也能过),但是运用归并排序的思想就可以达到 \(O(Nlog^2N)\) 的复杂度。

首先在外面把元素按照斜率 \(k\) 排序,然后开始 CDQ分治。

对于区间 \([l, r]\) ,把其中元素的编号按照与 \(mid\) 的大小进行分类,\(\leq mid\) 的分到左边,\(>mid\) 的分到右边,因为要用 \([l, mid]\) 中的点更新 \((mid, r]\),所以要先把这些点找出来。

接着递归进 \([l, mid]\) ,保证左区间已经被处理过了,才能更新右区间的元素。

现在左区间的点和信息都被处理好了,并且 \(x\) 是单调的(已经被处理好了,详见后述),加上右区间的元素的斜率 \(k\) 是单调的(还没有被处理过),所以就可以把左区间的点加入单调队列,然后去更新右区间的元素。

但是现在 \((mid, r]\) 中的元素只有来自 \([l, mid]\) 的贡献,可能取不到最优解,所以还要递归进 \((mid, r]\) 继续处理右区间。

最后不要忘了,要利用归并排序将 \([l ,r]\) 中 点的 \(x\) 变为单调的,这样才能保证前面操作的正确性。(可以理解为递归进一个区间后,这个区间内点的 \(x\) 就会被处理成单调的,可以进行后续的操作)

这就是 CDQ分治 的大致过程。

 

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注