洛谷P2900 [USACO08MAR]Land Acquisition G 题解

题目链接：P2900 [USACO08MAR]Land Acquisition G

题意：

Farmer John 准备扩大他的农场，眼前他正在考虑购买 $N$ 块长方形的土地。

如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 $3 \times 5$ 和一块 $5 \times 3$ 的土地，他只需要支付 $5 \times 5=25$ 元，比单买合算。

FJ 希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。

第一行一个整数 $N$（$1 \leq N \leq 5 \times 10^4$）。

接下来 $N$ 行，每行两个整数 $w_i$ 和 $l_i$，代表第 $i$ 块土地的长和宽。保证土地的长和宽不超过 $10^6$。

输出买下所有土地的最小费用。

斜率优化板子题。

首先可以推出来一个原始的转移方程

设 $f_i$ 表示买前 $i$ 个土地的最小花费

$f_i=\min\{f_{j} + \text{mxw}\{j+1,i\} \times \text{mxl}\{j+1,i\}\}$

但是这样子根本没法优化。

考虑怎样的土地可以对答案计算产生贡献（也就是必须计算花费的）

或者说，怎样的土地不能产生贡献

设土地 $i,j$ 满足 $w_i \ge w_j,~l_i \ge l_j$

则购买 $i$ 的时候， $j$ 可以与其并购并且不增加额外的花费

因此我们将所有物品按 $w_i$ 从大到小排序后所有能产生贡献的一定 $l_i$ 比之前大

即 $\forall i<j,w_i\ge w_j,l_i\le l_j$

至此，我们可以推出更好的转移方程

设 $f_i$ 表示买前 $i$ 个土地的最小花费

$f_i = \min\{f_j + w_{j+1}\times l_i \}$

当 $i$ 固定时，考虑怎样的一个 $j\,(i>j>k)$ 使得 $j$ 比 $k$ 更优

$f_{j}+w_{j+1}\times l_i \le f_k + w_{k+1} \times l_i \\f_j-f_k \le l_i \times (w_{k+1}-w_{j+1})$

由于 $w$ 是递减的，即 $w_{k+1} \ge w_{j+1}$ ，因此移项可得

$\dfrac{f_j-f_k}{w_{k+1}-w_{j+1}} \le l_i$

把右边的看作斜率，然后就是斜率优化

因为要求最小化 $f_i$ ，因此我们要维护一个下凸壳

关于凸壳的问题，可以看这篇 P3195 [HNOI2008]玩具装箱

时间复杂度 $O(n \log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e4+15)

struct node
{
    int x,y;
}a[N];
int n,st,en,q[N],f[N];
double slope(int i,int j)
{
    return 1.0*(f[i]-f[j])/(a[j+1].x-a[i+1].x);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i].x >> a[i].y;
    sort(a+1,a+1+n,[](node a,node b)
    {
        return a.x==b.x?a.y>b.y:a.x>b.x;
    });
    int t=0;
    for(int i=1; i<=n; i++)
        if(a[i].y>a[t].y) a[++t]=a[i];
    n=t; st=en=1;
    for(int i=1; i<=n; i++)
    {
        while(st<en&&slope(q[st],q[st+1])<=a[i].y)++st; // 去掉不优的点
        f[i]=f[q[st]]+a[q[st]+1].x*a[i].y;
        while(st<en&&slope(q[en-1],i)<slope(q[en-1],q[en]))--en; // 维护下凸壳
        q[++en]=i;
    }
    cout << f[n] << '\n';
    return 0;
}