YZOJ P3669 [USACO2008 Mar]土地购买

YZOJ P3669 [USACO2008 Mar]土地购买

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

难度:\(6.0\) (自评)

  • 题目描述

农夫 John 准备扩大他的农场,他正在考虑 \(N\) (\(1 \leq N \leq 1,000,000\)) 块长方形的土地。

每块土地的长宽满足 (\(1 \leq\) 宽 \(\leq 1,000,000\), \(1 \leq\) 长 \(\leq 1,000,000\))。每块土地的价格是它的面积,但 FJ 可以同时购买多块土地。

这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换。如果 FJ 买一块 \(3 \times 5\) 的地和一块 \(5 \times 3\) 的地,则他需要付 \(5 \times 5=25\)。

FJ 希望买下所有的土地,但是他发现分组来买这些土地可以节省经费。他需要你帮助他求出最小的经费。

  • 输入格式

输入文件的第 \(1\) 行一个数 \(N\), 表示土地块数。第 \(2\) 行至第 \(N+1\) 行,每行包含两个数,表示第 \(i\) 块土地的长和宽。

  • 输出格式

最小的可行费用。

  • 样例输入

  • 样例输出

 

 

 


 

 

 

wtcl \(O(N^2)\) 的 DP 都想不出来然后成功爆了零。

 

注意到土地的选择是分组的,组数没有限制,每一组可以包括的矩形也没有特殊的限制,这样范围太大了,无法进行处理。怎么办呢???

首先注意到的是,如果有出现某个矩形完全包含另一矩形的情况,那么那个小矩形就可以直接扔掉了。因为在选大矩形的同时选小矩形,那么代价不会变小;如果选择小的矩形,那么一定要选大的矩形,否则肯定是不优的。

换句话说,就是对于两个矩形 \(A, B\) ,若 \(\left(length_A \geq length_B\right) \land \left(width_A \geq width_B\right)\) ,那么矩形 \(B\) 就可以直接被删去,不需要进行处理。

处理的时候可以先以矩形的长为第一关键字,矩形的宽为第二关键字进行升序排序。因为这样随着 \(i\) 的增大,矩形的长都是非严格单调递增的,满足了 \(length_A \geq length_B\) ,所以接下来只要满足 \(width_A \geq width_B\)就可以了。(注意原序列 \(orect\) 和新序列 \(rect\) 不要搞混了)

这样就可以得到长非严格单增宽非严格单减的矩形序列(注意因为删去了递增的宽,所以宽是非严格单减的)。

有了这个性质,就可以推导出DP方程了。因为长、宽都是单调的,所以显然选择连续的一些矩形作为一组购买是最优的。

所以设 \(f_i\) 为购买到第 \(i\) 个矩形时,所耗最小的费用。转移 \(f_i=\min\limits_{0 \leq j < i}\{f_j+cost_{j+1, i}\}\) 。由于长、宽单调,所以 \(cost_{j+1, i}=width_{j+1} \cdot length_{i}\) 。

状态数 \(O(N)\) ,转移费用 \(O(N)\) ,所以时间复杂度为 \(O(N^2)\) 无法通过本题。

如果是稍有知识储备的人(可惜我不是)就会立刻发现 这个是个经典的 1D1D 的 DP斜率优化模型。

对于斜率优化,orzCJKimmortalCO 揭示了一种新的方法来理解它,我会在下面进行详细说明。

这是刚才推导的转移方程: \(f_i=\min\limits_{0 \leq j < i}\{f_j+w_{j+1} \cdot l_{i}\}\) ,现在我们要赋予它以几何意义。(时刻注意,这个方程的意义是对于一个 \(i\) 在 \(0 \leq j < i\) 范围内寻找最小的 \(f_j+w_{j+1} \cdot l_{i}\))

设 \(x_j=-w_{j+1}, y_j=f_j\) ,那么需要最小化的式子就变为了 \(y_j-x_j \cdot l_i\) 。同时还注意到直线的解析式为 \(y=kx+b\) ,那么截距 \(b=y-kx\) ,所以这个需要最小化的式子其实表示的是一条斜率为 \(l_i\) 的直线的截距

换句话说,把所有可以进行转移的 \(j\) 都表示为二维平面上的一个点 \(p_j=\left(x_j, y_j\right)\) ,我们需要做的就是在所有这样的点中,找到一个点,使经过它的斜率为 \(l_i\) 的直线的截距最小

好的,现在想象一条斜率固定的直线从下往上平移,当它第一次经过某个点 \(p_j\) 时,这时的截距肯定取到最小值。那么这个点 \(p_j\) 在什么地方呢?显然,它会在下凸壳上。设此时这条直线的斜率为 \(k\) ,\(p_j\) 到凸壳的上一个点的直线的斜率为 \(k_1\) ,\(p_j\) 到凸壳的下一个点的直线的斜率为 \(k_2\) ,那么 \(k \in [k_1, k_2]\) 。由于下凸壳上斜率单调递增,所以在单调栈上二分决策点就可以了。

但是由于这题 \(l_i\) 是单增的,也就意味着斜率都是单增的,稍加处理后直接取队头元素即可,不需要二分。

需要稍加注意的是,这里的 \(x_j\) 也是单增的,否则就需要 CDQ分治 或者 Splay 来维护。

说实话,我觉得上面的解释实在是太好了,值得多多思考和体会。

回到本题,剩下的工作只是维护下凸壳而已。

如果队头的前两个点的直线的斜率 比 当前的斜率 \(l_i\) 还,那么队头的那个点肯定是取不到了,因为这条直线会在到达第一个点之前先到达第二个点,所以弹出队头元素直到满足条件,这样就可以放心的取队头元素作为最小的 \(j\) 贡献给 \(i\) 。

之后就是维护下凸壳的常规操作。如果队尾两个点的直线的斜率最后一个点和当前需要加入的点的直线的斜率还,说明图形凹进去了,由于维护的是下凸壳,所以需要把队尾元素弹出直到满足条件,最后再把当前点加入。

有几个细节是值得注意的,比如要先加入 \(f_0\) 这个决策点,\(x_j=-w_{j+1}\) 等等。

 

 

 

 

 

发表回复

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