题目
题目描述
你可能已经听说过巴比伦塔的传说。现在这个传说的许多细节已经被遗忘。所以本着本场比赛的教育性质，我们现在会告诉你整个传说：
巴比伦人有n种长方形方块，每种有无限个，第i种方块的三边边长是xi,yi,zi。对于每一个方块，你可以任意选择一面作为底，这样高就随着确定了。举个例子，同一种方块，可能其中一个是竖着放的，一个是侧着放的，一个是横着放的。
他们想要用堆方块的方式建尽可能高的塔。问题是，只有一个方块的底的两条边严格小于另一个方块的底的两条边，这个方块才能堆在另一个上面。这意味着，一个方块甚至不能堆在一个底的尺寸与它一样的方块的上面。
你的任务是编写一个程序，计算出这个塔可以建出的最高的高度。v
输入输出格式
输入格式
输入会包含至少一组数据，每组数据的第一行是一个整数n(n<=30)，表示方块的种类数。
这组数据接下来的n行，每行有三个整数，表示xi,yi,zi。
输入数据会以0结束。
输出格式
对于每组数据，输出一行，其中包含组号(从1开始)和塔最高的高度。按以下格式：
Case : maximum height = __
输入输出样例
输入样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 1
10 20 30
2
6 8 10
5 5 5
7
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
6 6 6
7 7 7
5
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
0
|
输出样例
1
2
3
4
| Case 1: maximum height = 40
Case 2: maximum height = 21
Case 3: maximum height = 28
Case 4: maximum height = 342
|
题解
DAG上求最长路
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<cstdio>
#include<cstring>
#include<algorithm>
int n, blocks[35][3], d[35][3];
inline void GetDimensions(int* v, int b, int dim) {
int idx = 0;
for (register int i(0); i < 3; ++i)
if(i != dim) v[idx++] = blocks[b][i];
}
inline int dp(const int &i, const int &j) {
int& ans = d[i][j];
if(ans > 0) return ans;
ans = 0;
int v[2], v2[2];
GetDimensions(v, i, j);
for (register int a(0); a < n; ++a)
for (register int b(0); b < 3; ++b) {
GetDimensions(v2, a, b);
if(v2[0] < v[0] && v2[1] < v[1]) ans = std::max(ans, dp(a,b));
}
ans += blocks[i][j];
return ans;
}
int main(int argc, char **argv) {
register int cases(0);
while(scanf("%d", &n) == 1 && n) {
for (register int i(0); i < n; ++i) {
for (register int j(0); j < 3; ++j)
scanf("%d", &blocks[i][j]);
std::sort(blocks[i], blocks[i]+3);
}
memset(d, 0, sizeof(d));
int ans = 0;
for (register int i(0); i < n; ++i)
for (register int j(0); j < 3; ++j)
ans = std::max(ans, dp(i,j));
printf("Case %d: maximum height = %d\n", ++cases, ans);
}
return 0;
}
|