pku2241.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <stdlib.h>

typedef struct 
{
	int x, y, h;
} BOX;

BOX b[90];
int DP[100];
int N;

int cp(const void *a, const void *b)
{
	BOX *aa = (BOX *)a;
	BOX *bb = (BOX *)b;
	if (aa->x != bb->x)
	{
		return aa->x - bb->x;
	}
	return aa->y - bb->y;
}

int main()
{
	int i, t, j, k, max, ks;
	int eg[3];
	ks = 1;
	while (scanf("%d", &N) != -1 && N)
	{
		for (k = 0; k < N; k++)
		{
			scanf("%d %d %d", &eg[0], &eg[1], &eg[2]);
			for (i = 0; i < 3; i++)
			{
				for (j = i + 1; j < 3; j++)
				{
					if (eg[i] < eg[j])
					{
						t = eg[j];
						eg[j] = eg[i];
						eg[i] = t;
					}
				}
			}
			
			b[k * 3].x = eg[0];
			b[k * 3].y = eg[1];
			b[k * 3].h = eg[2];

			b[k * 3 + 1].x = eg[0];
			b[k * 3 + 1].y = eg[2];
			b[k * 3 + 1].h = eg[1];

			b[k * 3 + 2].x = eg[1];
			b[k * 3 + 2].y = eg[2];
			b[k * 3 + 2].h = eg[0];
		}
		memset(DP, 0, sizeof(DP));
		qsort(b, N * 3, sizeof(b[0]), cp);
		for (i = 0, k = 0; i < 3 * N; i++)
		{
			max = b[i].h;
			for (j = 0; j < i; j++)
			{
				if (b[i].x > b[j].x && b[i].y > b[j].y)
				{
					t = DP[j] + b[i].h;
					if (t > max)
					{
						max = t;
					}
				}
			}
			DP[i] = max;
			if (max > k)
			{
				k = max;
			}
		}
		printf("Case %d: maximum height = %d\n", ks++, k);
	}

	return 0;
}