Luogu P2900 [USACO08MAR]Land Acquisition G 题解

Luogu P2900 [USACO08MAR]Land Acquisition G 题解

Describe

题目链接

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

Solution

块土地的最小费用，那么有：

f_i=min(f_j w_{j 1}times l_{i})(0leq j <i)

优，则

f_j w_{j 1}times l_{i}leq f_k w_{k 1}times l_{i}

化简一下：

(f_j-f_k) l_itimes (w_{j 1}-w_{k 1})leq 0

即：

frac{f_k-f_j}{w_{j 1}-w_{k 1}}ge l_i

那么愉快的维护一个下凸壳即可。

Code

代码语言：javascript复制

#include<bits/stdc  .h>
#define LD double
using namespace std;
int n,m,q[1000010],l,r;
long long f[100010];
struct node{int w,l;}a[1000010];
inline int cmp(node x,node y){return x.w>y.w(x.w==y.w&&x.l>y.l);}
inline LD slope(int j,int k){
    return (LD)((LD)(f[k]-f[j]))/((LD)(a[j 1].w-a[k 1].w));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i  ) scanf("%d%d",&a[i].w,&a[i].l);
    sort(a 1,a n 1,cmp);
    for(int i=1;i<=n;i  )
        if(a[i].l>a[m].l) a[  m]=a[i];
    l=r=1;q[1]=0;
    for(int i=1;i<=m;i  ){
        while(l<r&&slope(q[l],q[l 1])<=a[i].l) l  ;
        f[i]=f[q[l]] 1ll*a[i].l*a[q[l] 1].w;
        while(l<r&&slope(q[r-1],q[r])>=slope(q[r],i)) r--;
        q[  r]=i;
    }
    printf("%lldn",f[m]);
}

ode

0 人点赞