UVA437 巴比伦塔 The Tower of Babylon

将一个长方体转换为六个长方体。

{x,y,z}=>{x,y,z},{x,z,y},{y,x,z},{y,z,x},{z,x,y},{z,y,x}

将这\(6n\)个长方体排序

inline int cmp(node x,node y){
      if(x.x==y.x)return x.y<y.y;
      retrun x.x<y.x;
}

然后随意\(dp\)就好了。

for(int i=1;i<=t;i++){
      dp[i]=a[i].z;
      for(int j=1;j<i;j++)
            if(a[i].x>a[j].x&&a[i].y>a[j].y)
                  f[i]=max(f[i],f[j]+a[i].z);
}

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
struct node{
    int x,y,z;
}a[maxn];
int n,t,kase,f[maxn],ans;
inline int cmp(node x,node y){
    if(x.x==y.x)return x.y<y.y;
    return x.x<y.x;
} 
int main(){
    while(scanf("%d",&n),n){
        int x,y,z;t=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&x,&y,&z);
            a[++t]=(node){x,y,z};
            a[++t]=(node){x,z,y};
            a[++t]=(node){y,x,z};
            a[++t]=(node){y,z,x};
            a[++t]=(node){z,x,y};
            a[++t]=(node){z,y,x};
        }
        sort(a+1,a+1+t,cmp);
        memset(f,0,sizeof(f));
        for(int i=1;i<=t;i++){
            f[i]=a[i].z;
            for(int j=1;j<i;j++)
                if(a[i].x>a[j].x&&a[i].y>a[j].y)
                    f[i]=max(f[i],f[j]+a[i].z);
        }
        ans=0;
        for(int i=1;i<=t;i++)
            ans=max(ans,f[i]);
        printf("Case %d: maximum height = %d\n",++kase,ans);
    }
    return 0;
}