这是一道几何题吧(大概
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; }