这是一道几何题吧(大概
n的范围很小 我们可以直接生成全排列来寻找堆叠碗最低的序列组合
两个碗的堆叠种类有6种(在代码里面都有注释 建议自己在纸上手画一遍
碗一个一个堆叠时 要计算与之前已经放的碗一起堆的高度
其中最高的高度就是真实高度(这一点是看别人题解才知道的.......
qwq 菜鸡没什么好说的了
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n,k[N];
double r1[N],r2[N],h[N],f[N];
double qg(int x,int y)
{
if(r2[x]<=r1[y]) return 0;///x全部在y里面
if(r1[x]>=r2[y]) return h[y];///x全部在y外面
if((r2[x]-r1[x])*h[y]<=(r2[y]-r1[y])*h[x])///x的斜率大于y
{
if(r1[x]<=r1[y]) return 0;///x能接触到y的底
return (r1[x]-r1[y])*h[y]/(r2[y]-r1[y]);///不能接触到y的底
}
if(r2[x]<=r2[y])return max(0.0,double(h[y]*(r2[x]-r1[y])/(r2[y]-r1[y])-h[x]));///x全部在y里面(x斜率小于y)
return max(0.0,double(h[y]-h[x]*(r2[y]-r1[x])/(r2[x]-r1[x])));///一部分在外面
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>h[i]>>r1[i]>>r2[i];///r1 下低 r2 上低
k[i]=i;
}
double ans=1000000000;
do
{
double ins=0;
for(int i=1;i<=n;++i)
{
f[i]=0;
for(int j=1;j<i;++j)f[i]=max(f[i],f[j]+qg(k[i],k[j]));
ins=max(ins,f[i]+h[k[i]]);
}
ans=min(ins,ans);
}
while(next_permutation(k+1,k+1+n));
cout<<ans<<endl;
return 0;
}

京公网安备 11010502036488号