因为碗的数量很少,直接全排列求所有叠放情况就行了,然后考虑两个碗之间的关系。
一共有四种情况
1,如果上面的碗的底比下面的碗口大,那就直接堆上去
2,如果上面的碗的碗口小于了下面的碗的底,那就放到下面的碗里面了
3,上面的碗斜率小于下面的碗,再看有没有放到碗底
4,下面的碗斜率小于上面的碗,看碗有没有完全放进去
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <queue> #include <cmath> #define ll long long #define pi 3.1415927 #define inf 0x3f3f3f3f #define mod 1000000007 using namespace std; #define _int __int128_t inline int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar(); return f*x; } void print(int x) { if(x < 0) {putchar('-');x = -x;} if(x/10) print(x/10); putchar(x%10+'0'); } int n,m,id[105]; struct node{ double r1,r2,h; }a[105]; double f[105]; double slope(int i) { return (a[i].r2-a[i].r1)/a[i].h; } double solve(int i,int j) { if(a[i].r1>a[j].r2) return a[j].h; if(a[i].r2<a[j].r1) return 0; if(slope(i)<=slope(j)){ if(a[i].r1<=a[j].r1) return 0; return a[j].h*(a[i].r1-a[j].r1)/(a[j].r2-a[j].r1); } if(a[i].r2>a[j].r2) return max(a[j].h-(a[j].r2-a[i].r1)/(a[i].r2-a[i].r1)*a[i].h,0.0); return max((a[i].r2-a[j].r1)/(a[j].r2-a[j].r1)*a[j].h-a[i].h,0.0); } int main () { int T,i,t,j,k,p; double sum=inf,res; cin>>n; for(i=1;i<=n;++i){ cin>>a[i].h>>a[i].r1>>a[i].r2; id[i]=i; } do{ res=0; for(i=1;i<=n;++i){ f[i]=0; for(j=1;j<i;++j){ f[i]=max(f[i],f[j]+solve(id[i],id[j])); } res=max(res,f[i]+a[id[i]].h); } sum=min(sum,res); } while(next_permutation(id+1,id+1+n)); print(sum+0.5); return 0; }