【bzoj1597】 土地购买

http://www.lydsy.com/JudgeOnline/problem.php?id=1597 (题目链接)

题意

　　购买n个矩形，每块土地的价格是它的面积，但可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽，求最少花费。

Solution

　　按照x单增，y单减排序，将可以相互包含的矩形去掉，易证每组在连续一段最优。

细节

　　。。

代码

// bzoj1597 #include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<cmath> #define LL long long #define inf 1e18 #define Pi acos(-1.0) #define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); using namespace std;const int maxn=50010; struct data {LL x,y;}a[maxn]; LL f[maxn]; int n,q[maxn];bool cmp(data a,data b) {return a.x==b.x ? a.y<b.y : a.x<b.x; } double slope(int i,int j) {return (double)(f[i]-f[j])/(double)(a[i+1].y-a[j+1].y); } int main() {scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y);sort(a+1,a+1+n,cmp);int tot=0;for (int i=1;i<=n;i++) {while (tot && a[i].y>=a[tot].y) tot--;a[++tot]=a[i];}n=tot;int l=1,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++;f[i]=f[q[l]]+a[i].x*a[q[l]+1].y;while (l<r && slope(q[r-1],q[r])<slope(q[r],i)) r--;q[++r]=i;}printf("%lld",f[n]);return 0; }

　　

转载于:https://www.cnblogs.com/MashiroSky/p/6014168.html

总结

以上是生活随笔为你收集整理的【bzoj1597】 土地购买的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。