Description
农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3×5的地和一块5×3的地,则他需要付5×5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.
Solution
思路是斜率优化,首先,对于两个土地i,j,如果X[j]<=X[i]&&Y[j]<=Y[i]那么可以直接把土地i排除掉
开始时把土地按X为第一关键字,Y为第二关键字升序排序,
\(dp[i]=min\{dp[j]+y[j+1]*x[i]\}\)
搞个斜率优化\(\frac{dp[j]-dp[k]}{y[j+1]-y[k+1]}>-x[i]\)
Code
#include <cstdio>
#include <algorithm>
#define N 50010
using namespace std;
struct info{
int x,y;
friend bool operator < (info a,info b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
}A[N];
int n,cnt,l,r,q[N];
long long dp[N];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
double slope(int k,int j){
return (1.0*(dp[j]-dp[k]))/(A[j+1].y-A[k+1].y);
}
void DP(){
l=r=1;q[1]=0;
for(int i=1;i<=n;++i){
while(l<r&&slope(q[l],q[l+1])>-A[i].x) l++;
int j=q[l];
dp[i]=dp[j]+A[j+1].y*1ll*A[i].x;
while(l<r&&slope(q[r],i)>slope(q[r-1],q[r])) r--;
q[++r]=i;
}
}
int main(){
n=read();
for(int i=1;i<=n;++i) A[i].x=read(),A[i].y=read();
sort(A+1,A+n+1);
for(int i=1;i<=n;++i){
if(A[i].y<=A[i+1].y) continue;
while(cnt&&A[cnt].y<=A[i].y) cnt--;
A[++cnt]=A[i];
}n=cnt;
DP();
printf("%lld\n",dp[n]);
return 0;
}