2018-03-30

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;