uva 437(最长递减子序列)

题意：给出有n种长方体的长宽高，假如有无数个这些长方体来摆放，要求如果一个长方体的长和宽都比下面的长方体小，那么就可以垒上去，问最多能垒多高。

题解：将所给出的某种长方体的所有高不同的情况都存储起来，然后按面积降序排列，按最长递减子序列的思想，将某个点当做最高点，更新最高的高度。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 35;
struct Block {
	int x, y, z;
}block[N * 3];
int f[N], n, t = 1, a, b, c;

int cmp(Block a, Block b) {
	return  a.x * a.y > b.x * b.y;
}

int main() {
	while (scanf("%d", &n) && n) {
		int k = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d%d%d", &a, &b, &c);
			block[k].x = a;
			block[k].y = b;
			block[k++].z = c;
			block[k].x = a;
			block[k].y = c;
			block[k++].z = b;
			block[k].x = b;
			block[k].y = c;
			block[k++].z = a;
		}
		sort(block, block + k, cmp);
		int res = -1;
		for (int i = 0; i < k; i++) {
			f[i] = block[i].z;
			for (int j = 0; j < i; j++) {
				if (block[j].x > block[i].x && block[j].y > block[i].y ||
					block[j].x > block[i].y && block[j].y > block[i].x)
					f[i] = f[i] > f[j] + block[i].z ? f[i] : f[j] + block[i].z;
			}
			if (f[i] > res)
				res = f[i];
		}
		printf("Case %d: maximum height = %d\n", t++, res);
	}
	return 0;
}