//解題思路：每一個立方體必然有 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
雪黛依夢 閱讀(722)
評論(0) 編輯 收藏 引用 所屬分類:
背包----貪心、回溯、分支界限