题解 P2589 【[ZJOI2006]碗的叠放】

· · 题解

先吐槽一下，我因为一些智障原因萎了很久

这是题目原图

我们首先需要知道指定两个碗叠放的状态，分情况讨论：

1、放在上方的碗底比下面的碗口还要大，那么多出来h_{up}的高度（必为正）

2、原图左边的情况，上方的碗底与下方碗壁接触h_{up}-h_{down}+h_{down}*\frac{r1_{up}-r1_{down}}{r2_{down}-r1_{down}}（可正可负）

3、原图右边上方的情况，下面的碗口与上面的碗壁相接h_{up}*\frac{r2_{up}-r2_{down}}{r2_{up}-r1_{up}}（必为0或正数）

4、如果一个碗可以完全放入另一个碗里，且只有碗底平面相接，为h_{inside}-h_{outside}（可正可负）

5、如果一个碗可以完全放入另一个碗里，但是里面的碗的碗口卡在了外面的碗壁上h_{outside}*\frac{r2_{inside}-r1_{outside}}{r2_{outside}-r1_{outside}}-h_{outside}（必为0或负数）

有了这些关系之后，暴力dfs就可以得出答案

每次判断某个碗的高度时要与已经放入的 每个 碗测一下（因为有些碗放的时候是凹进去的，高度会比外面那只低）

上代码

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define dd c=getchar()
inline int read(){
    int a=0,b=1,dd;
    while(!isdigit(c)){if(c=='-')b=-b;dd;}
    while(isdigit(c)){a=a*10+c-'0';dd;}
    return a*b;
}
#undef dd
int n;
int h[10],r1[10],r2[10];
bool vis[10];
double ans,f[10][10],deep[10];
int tp=0;
void dfs(int p){
    double x;
    if(p>n){
        x=0;
        for(int i=1;i<=n;i++)if(deep[i]>x)x=deep[i];
        ans=min(ans,x);
        return;
    }
    tp++;
    for(int i=1;i<=n;i++)if(!vis[i]){
        x=0;
        for(int j=1;j<=n;j++)if(vis[j])x=max(x,deep[j]+f[j][i]);
        vis[i]=1;
        deep[i]=x;
        //for(int i=1;i<=tp;i++)putchar('\t');
        //printf("%d %.6lf\n",i,x);
        dfs(p+1);
        vis[i]=0;
    }
    tp--;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        h[i]=read();
        r1[i]=read();
        r2[i]=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(r1[j]>=r2[i]){
                f[i][j]=h[j];
                continue;
            }
            f[i][j]=h[j]-h[i];
            if(r1[j]>=r1[i]){
                f[i][j]=max(f[i][j],h[j]-h[i]+h[i]*(double)(r1[j]-r1[i])/(double)(r2[i]-r1[i]));
            }
            if(r2[j]>=r2[i]){
                f[i][j]=max(f[i][j],h[j]*(double)(r2[j]-r2[i])/(double)(r2[j]-r1[j]));
            }else if(r2[j]>=r1[i]){
                f[i][j]=max(f[i][j],h[i]*(double)(r2[j]-r1[i])/(double)(r2[i]-r1[i])-h[i]);
            }
            //printf("%d %d %.6lf\n",i,j,f[i][j]);
        }
    }
    ans=1e9;
    for(int i=1;i<=n;i++){
        vis[i]=1;
        deep[i]=h[i];
        dfs(2);
        vis[i]=0;
    }
    printf("%.0lf\n",ans);
    return 0;
}