题目描述

小H有n个碗需要放进橱柜，她希望将他们叠起来放置。你知道每个碗都是规则的圆柱体，并且都是上宽下窄，你已经测量出了每个碗的两个半径及高，请你帮小H找出一种叠放顺序，使得叠放出来的碗堆的高度尽量小，比如：
图片说明
100%数据满足n < = 9。所有输入的数绝对值不超过1000。

输入描述:

第一行一个整数n，表示碗的数目。
以下n行，每行三个整数h，r1，r2。分别表示碗高及两个半径。其中r1<r2

输出描述:

仅一个数，表示最小的高度。答案四舍五入取整

题解

几何题是我头秃

我们首先分情况讨论一下两个碗放在一起时的状态：（以下讨论的均为放进去的碗的下碗底距离外面的碗的上碗底的高度）

1.如果上面的碗的碗底半径大于下面的碗的碗口半径，直接卡住。

2.如果上面的碗的碗口半径小于下面的碗的碗口半径，可以放进去，但有可能在下底面卡住。

3.下面的碗壁大于上面的碗壁的斜率，算出在哪里是卡住的，再加上即可。

4.下面的碗壁小于等于上面的碗壁的斜率

有了这些关系之后，就需要我们细心的列式子计算，分类讨论了。大家写代码的时候一定要注意，很可能写错一个符号，debug两小时

但要注意的是，每次判断某个碗的高度时要与已经放入的每个碗测一下（因为有些碗放的时候是凹进去的，高度会比外面那只低）

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=2e5+100;
/*
r1/(h+x)=r2/x
r1*x=r2*h+r2*x
x=r2*h/(r1-r2);

*/
int id[10];
double tmp[15];
struct node{
    double h,up,down;
}s[10];
double gethight(node a,node b){
    if(a.up<=b.down){
        return 0;
    }
    if(a.down>=b.up){
        return b.h;
    }
    if((a.up-a.down)*b.h<=(b.up-b.down)*a.h){
        if(a.down<=b.down){
            return 0;
        }
        double x=(b.down*b.h)/(b.up-b.down);
        return (a.down-b.down)*x/b.down;
    }
    if(a.up<=b.up){
        double x=(b.down*b.h)/(b.up-b.down);
        return max(0.0,(a.up-b.down)*x/b.down-a.h);
    }
    double x=(a.down*a.h)/(a.up-a.down);
    return max(0.0,b.h-(b.up-a.down)*x/a.down);
}
////////////////////////////////////////////////////////////////////////
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    repi(i,1,n){
        cin>>s[i].h>>s[i].down>>s[i].up;
        id[i]=i;
    }
    double ans=1e9,res=0;
    do{
        res=0;
        repi(i,1,n){
            tmp[i]=0;
            repi(j,1,i-1){
                tmp[i]=max(tmp[i],tmp[j]+gethight(s[id[i]],s[id[j]]));
            }
            //cout<<"tmp["<<i<<"]="<<tmp[i]<<endl;
            res=max(tmp[i]+s[id[i]].h,res);
            //cout<<res<<endl;
        }
        ans=min(ans,res);
    }while(next_permutation(id+1,id+n+1));
    cout<<(int)(ans+0.5)<<endl;
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/