https://blog.csdn.net/han_zhuang/article/details/77647818
原题链接： UVa-437
题目大意：
有n (n<=30)种立方体，每种立方体都有无穷个。要求选一些立方体摞成一个尽量高的塔（跟搭积木差不多，可以自行选择哪个边做高），但是使得每个立方体地面的长宽分别严格小于（长和宽都只能小于，不能等于）它下方底面的长和宽。
解题思路：
本题是使用动态规划求解DAG最长路径问题的一个例题，终点和起点未知。思考用什么来表示状态时，一开始想着用底面的长和宽表示，后来看了紫书上的分析：长和宽比较大，用底面长和宽的表示状态的时候需要开的数组比较大。所以给出了另外一种表示状态的方法，使用立方体的序号i和当前选择的高k作为状态的表示。
状态转移方程就是：d(i,k) = max(d(j,k') + k | i,j∈n,k∈3)。
整体思路就是：使用一个cube[n][3]二维数组来存储立方体，并且在输入时顺便对每个立方体的三条边进行排序。使用二维数组d[i][j]来表示：以第i个立方体的除j之外另外两条边为底的状态当做起点时，能达到的最大高度。由于不知道起点，所以需要对每种状态都要进行一次dp()，需要O(n)，dp在进行的时候又需要O(n),所以总共需要O(n²)。同时选出最大的d[i][j]。
代码：
1. #include<iostream>
2. #include<cstring>
3. #include<algorithm>
5. using namespace std;
7. const int MAXN = 30 + 5;
9. int cube[MAXN][3];
10. int d[MAXN][3], n;
12. bool can_stack(int a ,int b,int c,int d)//判断（c，d）状态能不能放在（a，b）状态之上
13. {
14. int p[2], q[2], j = 0, k = 0;//p：底, q：上边
15. for (int i = 0; i < 3; i++) {
16. if (i != b) p[j++] = cube[a][i];
17. if (i != d) q[k++] = cube[c][i];
18. }
19. return q[0] < p[0] && q[1] < p[1];//严格小于,由于已经排序，所以无需调换顺序比较
20. }
22. //计算以d(a,b)为底的状态的最大高度：以方块a的第b个边长为高,其他两条边为为底的状态
23. int dp(int a,int b)
24. {
25. if (d[a][b] > 0) return d[a][b]; //已该状态为起始的最大高度已经找到
26. d[a][b] = cube[a][b];
27. for (int i = 0; i < n; i++)
28. for (int j = 0; j < 3; j++)
29. if (can_stack(a, b, i, j))
30. d[a][b] = max(d[a][b], dp(i, j) + cube[a][b]);
31. return d[a][b];
32. }
34. int main()
35. {
36. //freopen("input.txt","r",stdin);
37. //freopen("output.txt","w",stdout);
38. int kase = 0;
39. while (cin >> n && n) {
40. for (int i = 0; i < n; i++) {//输入，并对每个立方体的边长进行排序
41. for (int j = 0; j < 3; j++) {
42. cin >> cube[i][j];
43. }
44. sort(cube[i], cube[i] + 3);
45. }
46. memset(d, 0, sizeof(d));
47. int max_hgt = 0;
48. for (int i = 0; i < n; i++) //对每个状态进行dp
49. for (int j = 0; j < 3; j++)
50. max_hgt = max(max_hgt, dp(i, j));
51. cout << "Case " << ++kase << ": maximum height = " << max_hgt << endl;
