题目：题目链接
思路：每个方块可以用任意多次，但因为底面限制，每个方块每个放置方式选一个就够了，以x y为底 z 为高，以x z为底 y 为高，以y z为底 x为高，因为数据量很小，完全可以把每一种当成DAG上的一个结点，然后建图找最长路径。
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <cstring> 6 #include <string> 7 #include <vector> 8 #include <map> 9 #include <set> 10 #include <queue> 11 #include <deque> 12 #include <stack> 13 #include <list> 14 15 #define FRER() freopen("in.txt", "r", stdin) 16 #define FREW() freopen("out.txt", "w", stdout) 17 18 #define INF 0x3f3f3f3f 19 20 using namespace std; 21 22 struct block { 23 int x, y, z; 24 block() {} 25 block(int x, int y, int z):x(x), y(y), z(z) {} 26 bool operator < (const block & other) const { 27 return (x < other.x && y < other.y) || (x < other.y && y < other.x); 28 } 29 }; 30 31 vector<block> vec; 32 33 int n, m, d[100]; 34 bool G[100][100]; 35 36 void init() { 37 vec.clear(); 38 int x, y, z; 39 for(int i = 0; i < n; ++i) { 40 cin >> x >> y >> z; 41 vec.push_back(block(x, y, z)); 42 vec.push_back(block(x, z, y)); 43 vec.push_back(block(y, z, x)); 44 } 45 m = n * 3; 46 memset(G, 0, sizeof(G)); 47 for(int i = 0; i < m; ++i) 48 for(int j = 0; j < m; ++j) 49 if(vec[i] < vec[j]) 50 G[i][j] = 1; 51 52 memset(d, 0, sizeof(d)); 53 } 54 55 int dp(int i, int h) { 56 if(d[i]) return d[i]; 57 int& ans = d[i]; 58 ans = h; 59 m = n * 3; 60 for(int j = 0; j < m; ++j) { 61 if(G[i][j]) 62 ans = max(ans, dp(j, vec[j].z) + h); 63 } 64 return ans; 65 } 66 67 68 int solve() { 69 int ans = -1; 70 for(int i = 0; i < m; ++i) 71 ans = max(ans, dp(i, vec[i].z)); 72 return ans; 73 } 74 75 int main() 76 { 77 //FRER(); 78 //FREW(); 79 ios::sync_with_stdio(0); 80 cin.tie(0); 81 82 int kase = 0; 83 while(cin >> n, n) { 84 init(); 85 cout << "Case " << ++kase << ": maximum height = " << solve() << endl; 86 } 87 88 return 0; 89 }