HDU 1069 Monkey and Banana (DP)

HDU 1069 Monkey and Banana

传送门

题意

有一堆方块（三维的），可以把它们叠在一起，

求这些方块所能达到的最大高度。

思路

注意到这个问题颇像LIS,
只是元素的key由一维的数字变成了二维的长和宽而已。
于是可以把一个方块拆成六个（且一个方块的六种摆放方式不会有两种同时被选入LIS中），
之后就可以按照LIS的方式去做了。

---

这里我用的是O（n^2）的LIS。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=30*6+10;
int tot;
int f[maxn];
struct node{
    int x,y,z;
    void get(int _x,int _y,int _z){
        x=_x;y=_y;z=_z;
    }
    bool operator <(const node&a)const{
        if(x==a.x)
            return y>a.y;
        return x>a.x;
    }
}a[maxn];
int check(node a,node b){
    return ((a.x<b.x)&&(a.y<b.y));
}
int main(){
//  freopen("CCC.in","r",stdin);
    int n,cnt=0;
    while(1){
        scanf("%d",&n);
        if(n==0)break;
        cnt++;
        tot=1;
        for(int i=1;i<=n;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            a[tot++].get(x,y,z);
            a[tot++].get(x,z,y);
            a[tot++].get(y,x,z);
            a[tot++].get(y,z,x);
            a[tot++].get(z,x,y);
            a[tot++].get(z,y,x);
        }
        n=tot-1;
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++)
            f[i]=a[i].z;
        for(int i=2;i<=n;i++)
            for(int j=1;j<i;j++)
                if(check(a[i],a[j])&&f[i]<f[j]+a[i].z)
                    f[i]=f[j]+a[i].z;
        int mx=0;
        for(int i=1;i<=n;i++)
            mx=max(mx,f[i]);
        printf("Case %d: maximum height = %d
",cnt,mx);    
    }
    return 0;
}