学步园

题目：monkey想吃banana，但是banana挂在一定的高度，现在有长宽高为，x，y，h的长方体，要你堆成一个台阶让monkey可以踩在上面，要求，上一层的 地面长和宽都要小于下层的，这样monkey在上台阶时才可以方便

分析：因为每个长方体都有无数个可以使用，故先对输入的x,y,h排序成t1，t2，t3，（t1<=t2<=t3）再把一个长方体拆成三个长宽高分别为,t3,t2,t1;    t3,t1,t2;    t2,t1,t3;

先按长排序，再按宽二级排序，对宽进行类似最长上升子序列，的dp，状态转移方程：

dp[i]=max(dp[j])+h;(1<=j<i)......

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{
	int x,y,h;
}arr[1000];
int dp[1000];
int cmp(node x,node y)
{
	if(x.x==y.x)
		return x.y<y.y;//升序
	else
		return x.x<=y.x;
}
int main()
{
	int n,t=1;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		int x,y,h,c=1;
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d %d",&x,&y,&h);
			int t1=max(max(x,y),h);
			int t2=min(min(x,y),h);
			int t3=x+y+h-t1-t2;//t2<=t3<=t1
			arr[c].x=t2;
			arr[c].y=t3;
			arr[c++].h=t1;
			arr[c].x=t3;
			arr[c].y=t1;
			arr[c++].h=t2;
			arr[c].x=t2;
			arr[c].y=t1;
			arr[c++].h=t3;
		}
		//dp[1]=arr[1].h;放错位置了
        sort(arr+1,arr+1+3*n,cmp);
		dp[1]=arr[1].h;
		for(int i=2;i<c;i++)
		{
		   /* int low=1,high=i-1,mid;
			while(low<=high)
			{
				mid=(low+high)/2;
				if(arr[i].x<dp[mid].x&&arr[i].y<dp[mid].y)
					high=mid-1;
				else if(dp[mid].x<arr[i].x&&dp[mid].y<arr[i].y)
					high=mid+1;
			}*/
			int ans=0;
		    for(int j=1;j<i;j++)
			{
				if(arr[i].x!=arr[j].x && arr[i].y>arr[j].y&&dp[j]>ans)
				{
					ans=dp[j];
				}
			}
			dp[i]=ans+arr[i].h;
		 }
		/*for(int i=1;i<c;i++)
			printf("%d****  \n",dp[i]);
		printf("\n");*/
		int ans=0;
		for(int i=1;i<c;i++)
			if(dp[i]>ans)
				ans=dp[i];
		printf("Case %d: maximum height = %d\n",t++,ans);
	}
	system("pause");
	return 0;
}