[ZJOI2006]BOWL 碗的叠放

题目描述

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

输入描述:

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

输出描述:

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

题意

给定 n 个碗,然后给出宽和高,问所有的碗叠放在一起,的最小高度多少?

思路

因为n很小，所以这里可以尝试直接暴力枚举，直接枚举所有的排列组合，计算高度即可。

因为画图水平有限，我这里图就直接偷了，原图博客在这里

要注意第二种情况，小碗在大碗里面，所以相当于底部升高了一部分

按照上面图的几种情况，分类判断计算就好（几何太麻烦了

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
inline void write(__int128 x) { if (!x) { putchar('0'); return; } char F[50]; __int128 tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 1e9+7;
const int maxn = 55;
#define stop system("pause")
#define PI acos(-1.0)
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
struct node{
    double h,r1,r2;
}bowl[10];
int id[15];
double temp[15];
double cal(int x,int y){
    if(bowl[x].r1>bowl[y].r2)  return bowl[y].h;
    if(bowl[x].r2<bowl[y].r1)  return 0;
    if((bowl[x].r2-bowl[x].r1)*bowl[y].h<=(bowl[y].r2-bowl[y].r1)*bowl[x].h){
       if(bowl[x].r1<=bowl[y].r1) return 0;
       return bowl[y].h*(bowl[x].r1-bowl[y].r1)/(bowl[y].r2-bowl[y].r1);   
    }  
    if(bowl[x].r2>bowl[y].r2){
        return max(0.0,bowl[y].h-bowl[x].h*(bowl[y].r2-bowl[x].r1)/(bowl[x].r2-bowl[x].r1));
    }
    return max(0.0,bowl[y].h*(bowl[x].r2-bowl[y].r1)/(bowl[y].r2-bowl[y].r1)-bowl[x].h);
}
int main(){
    int n = read();
    for(int i=1;i<=n;i++){
        bowl[i].h = read();bowl[i].r1 = read();
        bowl[i].r2 = read();id[i]=i;
    }
    double ans = 0x3f3f,res=0;
    do{
        res=0;
        for(int i=1;i<=n;i++){
            temp[i]=0;
            for(int j=1;j<i;j++){
                temp[i]=max(temp[i],temp[j]+cal(id[i],id[j]));
            }
            res=max(temp[i]+bowl[id[i]].h,res);
        }
        ans=min(ans,res);
    }while(next_permutation(id+1,id+1+n));
    cout<<(int)(ans+0.5)<<endl;

 }