[排序+DP]hdoj 1069：Monkey and Banana

大致题意：
    给你n种箱子，每种箱子都有各自的长宽高，每种箱子都有无限多个。如果一个箱子的长和宽都小于另一个箱子，那么这个箱子就可以放在那个箱子上面。求这n种箱子最多可以堆多高。

 

大致思路：

    首先排序，按照长和宽中最长的那个。保证如果如果箱子i可以放在箱子j上面的话则j<i。然后就是简单的DP~~

 

#include<cstring>
#include<cstdio>
#include<iostream>
#include<cmath>
#include <algorithm>
using namespace std;
const int nMax=1000;
class node{
    public:
    int big,sma,h;
}block[nMax];

bool cmp(node a,node b){
    if(a.sma<b.sma)return 0;
    if(a.sma==b.sma){
        if(a.big<=b.big)return 0;
        return 1;
    }
    return 1;
}

int dp[nMax];
int main(){
    int n,i,j,a,b,c,m,ans,cas=1;
    while(scanf("%d",&m)&&m){
        n=0;
        ans=0;
        while(m--){
            scanf("%d%d%d",&a,&b,&c);
            block[n].big=max(a,b);
            block[n].sma=min(a,b);
            block[n++].h=c;
            block[n].big=max(a,c);
            block[n].sma=min(a,c);
            block[n++].h=b;
            block[n].big=max(b,c);
            block[n].sma=min(b,c);
            block[n++].h=a;
        }
        sort(block,block+n,cmp);   //大->小
        for(i=0;i<n;i++){
            dp[i]=block[i].h;
        }
        for(i=0;i<n;i++){
            for(j=0;j<i;j++){
                if(block[j].big>block[i].big&&block[j].sma>block[i].sma){
                    dp[i]=max(dp[i],dp[j]+block[i].h);
                    ans=max(dp[i],ans);
                }
            }
        }
        printf("Case %d: maximum height = %d\n",cas++,ans);
    }
    return 0;
}