【每日一题】BOWL 碗的叠放
[ZJOI2006]BOWL 碗的叠放
https://ac.nowcoder.com/acm/problem/20464
BOWL 碗的叠放
解题思路：
n只有9的大小，因此我们可以枚举碗的拜访顺序。接下来就是判断碗要怎么叠加
我们可以考虑碗的斜边斜率的关系
1）如果两者相等，要么可以放进去要不就不能放进去，
2）如果要放的小于已经放的，同样要放的底边可以放到已放的底边或者不能放到已放的底边，同样是两种情况
3）大于，同样是两种情况就不做图了，自己应该可以画出来
接着就是根据以上可以放的情况来算下底面的高度，找到最小值即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct no
{
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;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>bowl[i].h>>bowl[i].r1>>bowl[i].r2;
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;
} 