Describe

题目链接

Farmer John 准备扩大他的农场，眼前他正在考虑购买 $N$ 块长方形的土地。
如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 $3 \times 5$ 和一块 $5 \times 3$ 的土地，他只需要支付 $5 \times 5=25$ 元， 比单买合算。
FJ 希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。

Solution

考虑$dp$，但是怎么$dp$呢？
很显然，这需要先预处理。
将土地按照$w_i$从小到大排序，那么$l_i$筛选一下，一定是从大到小排序，否则肯定可以省略。
设$f_i$表示前$i$块土地的最小费用，那么有：$$f_i=min(f_j+w_{j+1}\times l_{i})(0\leq j <i)$$
显然，这个式子可以斜率优化。
设$0\leq j<k<i$且$k$比$j$优，则$$f_j+w_{j+1}\times l_{i}\leq f_k+w_{k+1}\times l_{i}$$
化简一下：
$$(f_j-f_k)+l_i\times (w_{j+1}-w_{k+1})\leq 0$$
即：
$$\frac{f_k-f_j}{w_{j+1}-w_{k+1}}\ge l_i$$
那么愉快的维护一个下凸壳即可。

Code