每一个长方形都有六种放置形态，其实可以是三种，但是判断有点麻烦直接用六种了，然后按照底面积给这些形态排序，排序后就完全变成了LIS的问题。代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1818
struct Node
{
int x,y,z,area;
void init(int a,int b,int c)
{
x = a;
y = b;
z = c;
area = x*y;
}
} blo[N];
bool cmp(Node a,Node b)
{
return a.area > b.area;
}
int main()
{
int n,z,a,b,c,cnt,dp[N],ca=;
// freopen("1.in.cpp","r",stdin);
while(cin>>n)
{
if(n==) break;
cnt = ;
for(int i = ; i < n; i++)
{
cin>>a>>b>>c;
blo[cnt++].init(a,b,c);
blo[cnt++].init(b,a,c);
blo[cnt++].init(c,b,a);
blo[cnt++].init(b,c,a);
blo[cnt++].init(a,c,b);
blo[cnt++].init(c,a,b);
}
sort(blo,blo+cnt,cmp);
for(int i = ; i < cnt; i++) dp[i] = blo[i].z;
for(int i = ; i < cnt; i++)
{
for(int j = ; j < i; j++)
{
if(blo[i].x < blo[j].x && blo[i].y < blo[j].y)
{
dp[i] = max(dp[i],dp[j]+blo[i].z);
}
}
}
int ans = ;
for(int i = ; i < cnt;i++) ans = max(ans,dp[i]);
printf("Case %d: maximum height = %d\n",++ca,ans);
}
return ;
}