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}\) 等等。