P2900 [USACO08MAR] Land Acquisition G
题意
Farmer John 准备扩大他的农场，眼前他正在考虑购买 \(N\) 块长方形的土地。
如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 \(3 \times 5\) 和一块 \(5 \times 3\) 的土地，他只需要支付 \(5 \times 5=25\) 元， 比单买合算。
FJ 希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。
题解
回顾一下斜优板子。
首先做一个单调栈，得到一个宽递减，长递增的序列，这样就转化为了平常 \(dp\) 的样子，设 \(f_i\) 表示前 \(i\) 个矩形的最小代价。
\[f_i = \min f_j+w_ih_{j+1}
\]
注意到可以斜优，修改为这样。
\[f_j = -w_ih_{j+1}+f_i
\]
我们将 \((-h_{j+1},f_j)\) 看做上述一次函数中的一个点，我们要找一个点使得截距最小。
维护一个下凸包，其中两点之间斜率单调递增，令截距最小的点是和下一个点之间的斜率与给定斜率最接近的点。
如何维护下凸包?用单调栈维护，弹到上一条边的斜率小于当前斜率为止。
找到最接近的斜率可以用二分，但是注意到要查的斜率也递增，所以使用双端队列，队首斜率小于给定斜率就弹出就行了。
code