因为碗的数量很少,直接全排列求所有叠放情况就行了,然后考虑两个碗之间的关系。
一共有四种情况
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;
}
京公网安备 11010502036488号