[ZJOI2006]BOWL 碗的叠放

题意:给定n(n<=9)个碗,然后每个有r1,r2,h(r1<r2)三个属性,问所有的碗叠放在一起,的最小高度多少?如图叠放

题解:n<=9???阶乘枚举9!=362880,稳过..........
然后每次从下往上放,好计算,如果从上往下,像图右这种...........
然后对于每次放的情况,我们假设上面的杯子为1号杯子,下面为2号杯子

第一种情况:1号杯子可以直接放到2号杯子底部(灵魂画师....凑后看,大概这意思)

红蓝代表两种极端情况

第二种情况:右图1号位置和3号位置情况

第三种情况:左图的情况

需要计算在那些位置会卡住

第四种情况:右图2号位置和3号位置情况

然后对于每种情况更新新的碗

#include<bits/stdc++.h>
using namespace std;
struct data
{
    double a,b,c,d;
}a[21],b[21];
int n,c[21];
double x,y,z;
data putin(double a,double b,double c,double d)
{
    data aa;
    aa.a=a;
    aa.b=b;
    aa.c=c;
    aa.d=d;
    return aa;
}
double getxl(data a)
{
    return (a.d-a.b)/(a.c-a.a);
}
double work(data a,data b)//两个碗放置的高度 
{
    double p=a.b;
    if(b.a>=a.c)
    {
        return a.d;
    }
    a.b=0;
    a.d-=p;
    if(getxl(a)>getxl(b))
    {
        if(b.c>=a.c)
        {
            double k=a.d-(a.c-b.a)*getxl(b);
            return p+max(k,0.0);
        }
        double k=a.d-b.d-(a.c-b.c)*getxl(a);
        return p+max(k,0.0);
    }else{
        if(a.a>b.a)
        {
            return p;
        }
        double k=a.d-(a.c-b.a)*getxl(a);
        return p+max(k,0.0);
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf%lf",&x,&y,&z);
        a[i]=putin(y,0.0,z,x);
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=i;
    }
    double minn=1e9;
    while(1)//计算每种排列的总高度 
    {
        b[0]=putin(1e9,0.0,1e9,0.0);
        for(int i=1;i<=n;i++)
        {
            double maxn=0;
            for(int j=0;j<i;j++)
            {
                maxn=max(maxn,work(b[j],a[c[i]]));
            }
            b[i]=putin(a[c[i]].a,a[c[i]].b+maxn,a[c[i]].c,a[c[i]].d+maxn);//放好的碗 
        }
        double maxn=0;
        for(int i=1;i<=n;i++)
        {
            maxn=max(maxn,b[i].d);
        }
        minn=min(minn,maxn);
        if(!next_permutation(c+1,c+n+1))//下一种排列 
        {
            break;
        } 
    }
    printf("%.0lf\n",minn);
    return 0;
}