Posted on 2008-03-23 17:25
superman 阅读(267)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1093 C++ 00:00.01 848K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct Rect { int a, b, height; } rect[100];
8
9 int cmp(const void * a, const void * b)
10 {
11 Rect * c = (Rect*)(a);
12 Rect * d = (Rect*)(b);
13 if(c -> a == d -> a)
14 return c -> b - d -> b;
15 return c -> a - d -> a;
16 }
17
18 void swap(int & a, int & b)
19 {
20 a = a ^ b;
21 b = a ^ b;
22 a = a ^ b;
23 }
24
25 int main()
26 {
27 int Case = 0, n;
28 while((cin >> n) && n)
29 {
30 int x, y, z, count = 0;
31 for(int i = 0; i < n; i++)
32 {
33 cin >> x >> y >> z;
34 count++; rect[count].a = x; rect[count].b = y; rect[count].height = z;
35 count++; rect[count].a = x; rect[count].b = z; rect[count].height = y;
36 count++; rect[count].a = y; rect[count].b = z; rect[count].height = x;
37 }
38
39 for(int i = 1; i <= count; i++)
40 if(rect[i].a > rect[i].b)
41 swap(rect[i].a, rect[i].b);
42
43 qsort(rect + 1, count, sizeof(Rect), cmp);
44
45 int opt[100] = {0};
46 opt[1] = rect[1].height;
47 for(int i = 2; i <= count; i++)
48 {
49 for(int j = 1; j < i; j++)
50 if(rect[i].a > rect[j].a && rect[i].b > rect[j].b)
51 opt[i] >?= opt[j];
52 opt[i] += rect[i].height;
53 }
54
55 int max = 0;
56 for(int i = 1; i <= count; i++)
57 max >?= opt[i];
58 cout << "Case " << ++Case << ": maximum height = " << max << endl;
59 }
60
61 return 0;
62 }
63