「Luogu 2900」Land Acquisition

发表于 | | 阅读次数:
字数统计: 809 字

Description

题目链接：Luogu 2900

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

数据范围：$1\le n\le 5\times 10^4$，$1\le w_i,l_i\le 10^6$

Solution

我们首先可以发现一个性质：如果对于土地 $i,j$ 满足 $w_i\ge w_j$ 且 $l_i\ge l_j$，那么土地 $j$ 显然是无用的。那么最终有用的土地，如果在宽递减的前提下，一定是长递增的。这个过程可以通过排序简单预处理。

假设我们已经得到 $n$ 块土地满足 $w_i\le w_{i-1},l_i\ge l_{i-1}$，我们可以证明每一组土地一定是连续的一段。这个证明基本是显然的，因为我们可以将一块土地并入前后的组别，使得这块土地不需要额外花费。

由此，我们可以简单推出 $\text{DP}​$ 方程：$f_i=\min\{f_j+w_{j+1}\times l_i\}\quad (0\le j<i)​$，但是这个转移是 $O(n^2)​$ 的，不能通过本题。

其实这个东西是有决策单调性的，我们考虑斜率优化。

我们任取 $j,k$ 满足 $0\le k<j<i$，如果此时 $j$ 比 $k$ 要更好，那么有如下不等式：

由于宽是递减的，那么 $w_{k+1}\ge w_{j+1}$，可以直接移项得到：

显然我们只要维护一个下凸壳就可以斜率优化啦！

时间复杂度：$O(n\log n)$（瓶颈竟然在排序上 QAQ）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
#include <cstdio>
#include <algorithm>

const int N=5e4+5;
int n,q[N];
long long f[N];
struct Land {
    int x,y;
    bool operator < (const Land &b) const {
        return x==b.x?y>b.y:x>b.x;
    }
} a[N];

void init() {
    std::sort(a+1,a+n+1);
    int m=0;
    for(int i=1;i<=n;++i) if(a[i].y>a[m].y) a[++m]=a[i];
    n=m;
}
double slope(int i,int j) {
    return 1.0*(f[i]-f[j])/(a[j+1].x-a[i+1].x);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
    init();
    int l=1,r=0;
    q[++r]=0;
    for(int i=1;i<=n;++i) {
        while(l<r&&slope(q[l],q[l+1])<=a[i].y) ++l;
        f[i]=f[q[l]]+1LL*a[q[l]+1].x*a[i].y;
        while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) --r;
        q[++r]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}
0%