ZOJ 1093 Monkey and Banana

ZOJ 1093 Monkey and Banana

題意：給你n個規格的磚塊，告訴你它的長、寬、高，每種規格的磚都有無數塊，長寬小的磚塊（嚴格小於，不能等於）可以疊在長寬大的磚塊上，問你最多能疊多高。

思路：告訴你一種規格的磚其實給了你三種規格的磚，因為磚是可以翻轉的，長寬高可以變化的；

以長為第一變量，寬為第二變量，從大到小排序，這樣墊在第n塊磚下面的只能從前n-1塊選擇，選擇最大值，累加高度即可。

代碼如下：

#include 
#include 
#include 
#include 
const int N = 35;
using namespace std;
int n;
int dp[3*N];

struct node
{
	int x, y, z;
	bool operator< (const node &rhs) const{
		if(x != rhs.x) return x > rhs.x;
		return y > rhs.y;
	}
}block[3*N];

int main()
{
	int cnt = 1;
    while(~scanf(%d, &n))
    {
    	int a, b, c;
    	if(n == 0) break;
        for(int i = 0, x, y, z; i < 3 * n; i ++)
        {
        	scanf(%d%d%d, &x, &y, &z);
        	a = max(max(x, y), z);
        	c = min(min(x, y), z);
        	b = (x + y + z) - (a + c);
        	block[i].x = a, block[i].y = b, block[i].z = c;
        	block[++i].x = a, block[i].y = c, block[i].z = b;
        	block[++i].x = b, block[i].y = c, block[i].z = a;
        }
        sort(block, block + 3 * n);
        int maxn;
        for(int i = 0; i < 3*n; i++)
        {
        	maxn = 0;
        	for(int j = 0; j < i; j++)
        	{
        		if(block[j].x > block[i].x && block[j].y > block[i].y &&  block[j].z > maxn)
        		{
        			maxn = block[j].z;
        		}
        	}
        	block[i].z += maxn;
        }
        maxn = 0;
        for(int i = 0; i < 3*n; i++)
        {
        	if(maxn < block[i].z)
        	{
        		maxn = block[i].z;
        	}
        }
        printf(Case %d: maximum height = %d
, cnt, maxn);
        cnt ++;
    }
    return 0;
}