hdu 1069 Monkey and Banana(dp 最长上升子序列)

http://acm.hdu.edu.cn/showproblem.php?pid=1069

题意：有n种类型的木块，木块是长方体，已知每种长方体的长宽高，且每种木块的数量是无限的。问这些木块能够摞起来的最高高度，摞起来的规则是上面的木块的长和宽必须严格小于下面木块的长和宽。

思路：把每种木块分成六种木块，然后对x排序，再对x和y求类似于最长上升子序列。这里dp对应的不是个数，而是摞起来的最高高度。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

struct node
{
int x,y,z;
bool operator < (const struct node &tmp)const
{
if(x == tmp.x)
return y < tmp.y;
return x < tmp.x;
}
}rec[200];

int cnt;
int dp[200];
void init(int x, int y, int z)
{
rec[++cnt] = (struct node){x,y,z};
rec[++cnt] = (struct node){x,z,y};
rec[++cnt] = (struct node){y,x,z};
rec[++cnt] = (struct node){y,z,x};
rec[++cnt] = (struct node){z,x,y};
rec[++cnt] = (struct node){z,y,x};
}

int main()
{
int n,x,y,z;
int item = 1;
while(~scanf("%d",&n) &&n)
{
cnt = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d %d %d",&x,&y,&z);
init(x,y,z);
}
sort(rec+1,rec+1+cnt);

int ans = -1;

for(int i = 1; i <= cnt; i++)
{
dp[i] = rec[i].z;
for(int j = 1; j < i; j++)
{
if(rec[i].x > rec[j].x && rec[i].y > rec[j].y && dp[i] < (dp[j]+rec[i].z))
dp[i] = dp[j]+rec[i].z;
}
}

for(int i = 1; i <= cnt; i++)
{
if(ans < dp[i])
ans = dp[i];
}

printf("Case %d: maximum height = ",item++);
printf("%d\n",ans);

}
return 0;
}