【bzoj1597- [Usaco2008 Mar]土地购买】斜率优化

【597】[Usaco2008 Mar]土地购买

【题目描述】

有N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3×5的地和一块5×3的地,则他需要付5×5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费。

【输入格式】

第1行: 一个数: N

第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽。

【输出格式】

求最小的可行费用。

Sample Input

100 1

15 15

20 5

1 100

Sample Output

500

HINT

FJ分3组买这些土地: 第一组:100×1, 第二组1×100, 第三组20×5 和 15×15 plot. 每组的价格分别为100,100,300, 总共500

给定一些矩形，分组购买，一组的价格是其中最大的长*最大的宽。

n<=50000

一开始并没有思路。。。

首先，我们考虑没有贡献的矩形——对于x,如果存在a[y]>=a[x] && b[y]>=b[x]，则x是无用的。排序去掉。

排序就先按x排序大到小，再按y排序大到小。

出现排序后x,y,z矩形，x能不能套y但能套z的话，那y也能套z，是不会错的。。

最后一定是a递减，b递增。

so：

f[i]=f[j]+a[j+1]*b[i]

然后用斜率优化。

这个是把除法改成乘法的。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long LL;

 const int N=;

 int n,pl,Q[N];

 LL l=,r=,ai,xj,bj,j,f[N];

 struct node{

     LL a,b;

     bool bk;

 }p[N];

 // f[i]=f[j]+a[j+1]*b[i]

 // ai=b[i]

 // xj=a[j+1]

 // bj=f[j]

 LL XX(int i,int j){return p[i+].a-p[j+].a;}

 LL YY(int i,int j){return f[i]-f[j];}

 double X(int i){return p[i+].a;}

 double Y(int i){return f[i];}

 double find_k(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}

 bool cmp(node x,node y){

     if(x.a!=y.a) return x.a>y.a;

     return x.b>y.b;

 }

 bool judge_1()

 {

     LL tx=XX(Q[l],Q[l+]),ty=YY(Q[l],Q[l+]);

     if(tx>=) return ty>=((-ai)*tx);

     return ty<=((-ai)*tx);

 }

 bool judge_2(int i)

 {

     LL t0=YY(Q[r],Q[r-]),t1=XX(Q[r],Q[r-]),t2=YY(i,Q[r]),t3=XX(i,Q[r]);

     if(t1<) t0=-t0,t1=-t1;

     if(t3<) t2=-t2,t3=-t3;

     return (t0*t3)<(t1*t2);

 }

 int main()

 {

     freopen("a.in","r",stdin);

     // freopen("acquire.in","r",stdin);

     // freopen("acquire.out","w",stdout);

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%lld%lld",&p[i].a,&p[i].b);

         p[i].bk=;

     }

     sort(p+,p++n,cmp);

     j=;

     for(int i=;i<=n;i++)

     {

         if(p[i].a<=p[j].a && p[i].b<=p[j].b) p[i].bk=;

         else j=i;

     }

     pl=;

     for(int i=;i<=n;i++)

         if(p[i].bk) p[++pl]=p[i];

     for(int i=;i<=pl;i++)

     {

         ai=p[i].b;

         while(l<r && judge_1()) l++;/*find_k(Q[l],Q[l+1])>=(-ai)*/

         j=Q[l];

         xj=p[j+].a;

         bj=f[j];

         f[i]=ai*xj+bj;

         while(l<r && judge_2(i)) r--;/*find_k(Q[r],Q[r-1])<find_k(i,Q[r])*/

         Q[++r]=i;

     }

     printf("%lld\n",f[pl]);

     return ;

 }

巴特西

【bzoj1597- [Usaco2008 Mar]土地购买】斜率优化

最新文章

热门文章