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;
}