[ZJOI2006]BOWL 碗的叠放

题目：
给与你n只碗，每只碗上宽下窄，告诉你上下半径和高度，请你求出n只碗叠放的高度最小为多少？

思路：
由于n<=9,所以可以直接枚举碗的顺序，求高度。
我们可以对两只碗不同情况的叠加情况（从边的斜率和上下半径考虑）进行分析，维护下底高度。

代码：

#include <bits/stdc++.h>
#define inf 1000000007
#define eps 0.000001
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn=100005;

struct w
{
    double h, r1, r2, k;
}w[15];
int a[15];

double fun(int i,int j)
{
    if(w[i].r1>=w[j].r2)
    {
        return w[j].h;
    }
    if(w[i].r2<=w[j].r1)
    {
        return 0;
    }
    if(w[i].k<w[j].k&&w[i].r2>=w[j].r2)
    {
        return max(w[j].h-(w[j].r2-w[i].r1)*w[i].k,0.0);
    }
    if(w[i].k<w[j].k&&w[i].r2<w[j].r2)
    {
        return max(0.0,(w[i].r2-w[j].r1)*w[j].k-w[i].h);
    }
    if(w[i].k==w[j].k)
    {
        if(w[i].r1<=w[j].r1)
        {
            return 0;
        }
        else
        {
            return (w[i].r1-w[j].r1)*w[i].k;
        }
    }
    if(w[i].k>w[j].k&&w[i].r1<=w[j].r1)
    {
        return 0;
    }
    if(w[i].k>w[j].k&&w[i].r1>w[j].r1)
    {
        return (w[i].r1-w[j].r1)*w[j].k;
    }
    return 0;
}
double tom[15];

int main()
{
    int n;
    double ans=inf;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        a[i]=i;
        scanf("%lf%lf%lf",&w[i].h,&w[i].r1,&w[i].r2);
        w[i].k=w[i].h/(w[i].r2-w[i].r1);
    }
    do
    {
        double z=0;
        for(int i=1;i<=n;i++)
        {
            tom[i]=0;
            for(int j=1;j<i;j++)
            {
                tom[i]=max(tom[i],tom[j]+fun(a[i],a[j]));
            }
            z=max(tom[i]+w[a[i]].h,z);
        }
        ans=min(z,ans);
    }while(next_permutation(a+1,a+n+1));
    printf("%.0f\n",ans);
    return 0;
}