洛谷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;
}