//解题思路：每一个立方体必然有 3 个面积，所以 N 种类型的立方体，必然有 3 * N 个面积组合
//将所有的面积从小到大排列之后，每组面积必然对应一个高的值，依据题意，要使高之和最大，所
//以这个问题就转化成了求最长子列和的最大值
1
#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5//定义一个结构体存立方体的面积 和 边长
6struct cube
7
{
8
int x;
9 int y;
10 int z;
11 int area;
12
}b[200]; //结构体变量
13
14//这是调用qsort 函数时必须要用的
15int compare(const void* a,const void* b)
16{
17 return (*(cube *)a).area-(*(cube *)b).area; //如果 < 则返回负数 如果 = 则返回0 如果 > 则返回 1
18}
19
20// 判断上面的两条边都要 < 下面的两条边
21int com (cube a, cube b)
22{
23
if ( (a.x < b.x && a.y < b.y) || (a.y < b.x && a.x < b.y) ) 如：10 20 与 40 50
24
return 1;
25
26
else
27
return 0;
28
}
29
30int main ()
31{
32 int sum[200];
33
34 //用来控制下标的
35
int dir[3][3] = { {0, 1, 2}, {0, 2, 1}, {1, 2, 0} };
36
37 int n;
38 int a[3];
39 int count = 0;
40 while (scanf ("%d", &n))
41 {
42 if (!n)
43 break;
44 int num = 0;
45 memset (sum, 0, sizeof (sum));
46 for (int i = 0; i < n; i ++)
47 {
48 scanf ("%d%d%d", &a[0], &a[1], &a[2]); //读入输入的三个数据
49
50 for (int j = 0; j < 3; j ++) //将所有可能的 立方体构成 存入到数组 b 中
51 {
52 b[num].x = a[ dir[j][0] ];
53 b[num].y = a[ dir[j][1] ];
54 b[num].z = a[ dir[j][2] ];
55 b[num].area = b[num].x * b[num].y;
56 num ++; //错点
57
}
58
59 }
60
61 //对 b 数组按面积进行快速排序
62 qsort (b, n * 3, sizeof (b[0]), compare);
63
64 /**//*
65 测试排序是否正确
66 for (int i = 0; i < 3 * n; i ++)
67 {
68 printf ("%d\t%d\t%d\t%d\n",b[i].x, b[i].y, b[i].z, b[i].area);
69 }*/
70
71 //在满足题目条件：上面的两条边都要 < 下面的两条边的情况下找到最大的高的和
72 sum[0] = b[0].z;
73 for (int i = 1; i < 3 * n; i++)
74 {
75 int temp = 0;
76 for (int j = 0; j < i; j ++)
77 {
78 if ( sum[j] > temp && ( com(b[j],b[i]) ) ) //要比较的高的值 满足题目的条件 累加求和
79 {
80 temp = sum[j];
81 }
82 }
83 sum[i] = temp + b[i].z;
84
85 //printf ("%d\t",sum[i]);
86 }
87
88 //printf ("\n");
89
90 //输出高的和
91 int max = -1;
92 for (int i = 0; i < 3 * n; i ++)
93 {
94 if (max < sum[i])
95 max = sum[i];
96 }
97
98 printf ("Case %d: maximum height = %d\n", ++count , max);
99
100 }
101
102 return 0;
103}
104
posted on 2010-08-16 10:03
雪黛依梦 阅读(709)
评论(0) 编辑 收藏 引用 所属分类:
背包----贪心、回溯、分支界限