1438.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 58 行

/*  This Code is Submitted by wywcgs for Problem 1438 on 2006-01-10 at 23:16:17 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 256;
const int N_MAX = 32;
const int INF = 200000000;

class Brick {
public:
	int l, w, h;
	void make(int, int, int);
	bool over(const Brick&) const;
	bool operator <(const Brick&) const;
};
void Brick::make(int cl, int cw, int ch) {
	l = cl, w = cw, h = ch;
}
bool Brick::over(const Brick& b) const {
	return l > b.l && w > b.w;
}
bool Brick::operator <(const Brick& b) const {
	return l > b.l;
}

int main()
{
	Brick brick[MAX];
	int mh[MAX];
	int i, j, t, n;

	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		int bn = 0;
		for(i = 0; i < n; i++) {
			int e[3];
			scanf("%d %d %d", &e[0], &e[1], &e[2]);
			sort(e, e+3);
			do {
				brick[bn++].make(e[0], e[1], e[2]);
			} while(next_permutation(e, e+3));
		}
		sort(brick, brick+bn);
		memset(mh, 0, sizeof(mh));
		int tall = 0;
		for(i = 0; i < bn; i++) {
			mh[i] = brick[i].h;
			for(j = 0; j < i; j++)
				if(brick[j].over(brick[i])) 
					mh[i] = max(mh[i], mh[j]+brick[i].h);
			tall = max(tall, mh[i]);
		}
		printf("Case %d: maximum height = %d\n", t, tall);
	}
	
	return 0;
}