每块土地的长和宽分别用数组 l l 和数组
表示。
每次买一组土地,需要的花费是 最大的长 × × 最大的宽,所以如果存在土地 i i 和
,满足 l[j]≥l[i] l [ j ] ≥ l [ i ] 且 h[j]≥h[i] h [ j ] ≥ h [ i ] ,土地 i i 就不会对答案产生影响。
因此,我们先将土地按长度从小到大排序,若长度相同按宽度从小到大排序。然后维护一个栈,将排序后的土地按次序加入,每次处理一块土地时先把当前栈中宽小于等于当前土地的土地删除。最后栈中留下的就是会对答案产生影响的土地。
我们可以发现,剩下的土地是按宽度降序排列的,那么给土地分组时一定是取连续的一段。因为这组土地的花费为第一块土地的宽度
最后一块土地的长度,如果从中间分出一段来,会保留原来的花费并产生新的花费。
之后就是斜率优化 dp d p 了,根据直线的交点的横坐标大小来判断优劣,我用了乘法来解决精度问题。
代码:
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define rt return
#define N 1000005
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
il int read(){int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=(x+(x<<2)<<1)+c-48;return x*f;
}
struct A{ll w,l;
}a[N];
ll f[N],k[N],b[N],q[N];
int n,cnt,h=1,t=1;
il bool cmp(A x,A y){rt (x.l==y.l)?x.w<y.w:x.l<y.l;
}
il double calc(int i,int j){rt f[j]+a[j+1].w*a[i].l;}
il bool slope(int x,int y,int z){rt (b[z]-b[x])*(k[y]-k[x])-(b[y]-b[x])*(k[z]-k[x])>=0;}
int main(){n=read();for(int i=1;i<=n;++i) a[i].w=read(),a[i].l=read();sort(a+1,a+n+1,cmp);for(int i=1;i<=n;++i){while(cnt&&a[i].w>=a[cnt].w) --cnt;a[++cnt].w=a[i].w,a[cnt].l=a[i].l;}k[0]=a[1].w;for(int i=1;i<=cnt;++i){while(h<t&&calc(i,q[h])>=calc(i,q[h+1])) ++h;f[i]=calc(i,q[h]),k[i]=a[i+1].w,b[i]=f[i];while(h<t&&slope(q[t-1],q[t],i)) --t;q[++t]=i;}return !printf("%lld",f[cnt]);;
}