【BZOJ1859】【ZJOI2006】碗的叠放

题目大意：给你n个碗，求如何堆叠，使得它们的总高度最低。

首先，我们枚举碗的叠放顺序。

假设我们已经堆好了前i个碗，那么在堆第i+1个碗时，我们要将第i+1个碗与前i个碗比较，确定第i+1个碗的离地高度。

对于第i个碗和第j个碗的比较，我们分五种情况讨论（以下画图只画半个碗）：

	上方的碗底比下方的碗顶大，直接放上去即可
	上方的碗底比下方碗底小，直接放上去即可
	上方的碗边缘斜率小于下方的碗，且上方的碗比下方的碗大，的计算出其中一个碗的斜率，然后卡位即可
	情况和上图类似，也是直接卡位即可。
	上方的碗边缘斜率大于下方的碗，也是直接卡位。

具体的细节可以看我的代码。

然后请一定要仔细检查所有细节（我错了一个字母调了2h）

 #include<bits/stdc++.h>

 #define M 10

 using namespace std;

 struct node{

     double a,b,c,d;

     node(){a=b=c=d=;}

     node(double aa,double bb,double cc,double dd){

         a=aa; b=bb; c=cc; d=dd;

     }

     double xl(){return (d-b)/(c-a);}

     friend double operator -(node a,node b){

         double p=a.b; a.b-=p; a.d-=p;

         //if(a.a>=b.a&&a.c>=b.c) return p;

         if(a.c<=b.a) return p+a.d;

         if(a.xl()>b.xl()){

             if(b.c>=a.c){

                 double k=a.d-(a.c-b.a)*b.xl();

                 k=max(k,.);

                 return p+k;

             }

             double k=a.d-b.d-(a.c-b.c)*a.xl();

             k=max(k,.);

             return p+k;

         }else{

             if(b.a<=a.a) return p;

             double k=a.d-(a.c-b.a)*a.xl();

             k=max(k,.);

             return p+k;

         }

     }

 }a[M],s[M];

 int n,p[M]={};

 int main(){

     scanf("%d",&n);

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

         double x,y,z; cin>>x>>y>>z;

         a[i]=node(y,,z,x);

     }

     for(int i=;i<=n;i++) p[i]=i;

     double minn=1e10;

     while(){

         memset(s,,sizeof(s));

         s[]=node(1e20,,1e21,);

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

             double maxn=;

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

             maxn=max(maxn,s[j]-a[p[i]]);

             s[i]=node(a[p[i]].a,maxn,a[p[i]].c,a[p[i]].d+maxn);

         }

         double maxn=;

         for(int i=;i<=n;i++) maxn=max(maxn,s[i].d);

         if(maxn<minn)

         minn=min(minn,maxn);

         if(!next_permutation(p+,p+n+)) break;

     }

     printf("%.0lf\n",minn);

 }

巴特西

【BZOJ1859】【ZJOI2006】碗的叠放

最新文章

热门文章