HDU 1069 Monkey and Banana

題意：把給定的長方體（不限）疊加在一起，疊加的條件是，上面一個長方體的長和寬都比下面長方體的長

和寬短；求這些長方體能疊加的最高的高度.（其中（3，2，1）可以擺放成（3，1，2）、（2，1，3）等）.

思路：其實就是求最長的單調遞減序列。在長和寬的遞減下，求最大能得出的最大高度了。

[cpp] 
#include<iostream> 
#include<cstdio> 
#include<algorithm> 
#include<cstring> 
using namespace std; 
struct node 
{ 
    int l,w,h; 
}box[111]; 
int dp[111]; 
bool cmp(node a,node b) 
{ 
   if(a.l>b.l) return true; 
   if(a.l==b.l&&a.w>b.w) return true; 
   return false; 
} 
int main() 
{ 
    int d[3],n,i,j,c=1,k,sumh; 
    while(scanf("%d",&n)!=EOF&&n) 
    { 
        k=0; 
        for(i=0;i<n;i++) 
        { 
            scanf("%d%d%d",&d[0],&d[1],&d[2]);  
            sort(d,d+3); 
            //將數據轉換成多種形式的矩形體 
            box[k].l=d[2];box[k].w=d[1];box[k].h=d[0];k++; 
            box[k].l=d[2];box[k].w=d[0];box[k].h=d[1];k++; 
            box[k].l=d[1];box[k].w=d[0];box[k].h=d[2];k++;    
        }  
        sort(box,box+k,cmp); 
        for(i=0;i<k;i++) dp[i]=box[i].h; 
        for(i=k-2;i>=0;i--) 
            for(j=i+1;j<k;j++) 
            { 
               if(box[i].l>box[j].l&&box[i].w>box[j].w)//最大遞減dp 
                   if(dp[i]<dp[j]+box[i].h) 
                       dp[i]=dp[j]+box[i].h; 
            } 
            sumh=dp[0]; 
            for(i=0;i<k;i++) 
                if(sumh<dp[i]) sumh=dp[i]; 
            printf("Case %d: maximum height = %d\n",c++,sumh); 
    } 
   return 0; 
}