fork(1) download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Box
  5. {
  6. int l;
  7. int w;
  8. int h;
  9. };
  10.  
  11. int compare(const void* a, const void* b)
  12. {
  13. return ((*(Box *)b).l)*((*(Box *)b).w) - ((*(Box *)a).l)*((*(Box *)a).w);
  14. }
  15.  
  16. int maxBoxHeight(Box arr[], int n)
  17. {
  18. Box rot[3*n];
  19. int temp;
  20. int r=0;
  21.  
  22. for(int i=0; i<n; i++)
  23. {
  24. rot[r] = arr[i];
  25. r++;
  26.  
  27. rot[r].h = arr[i].l;
  28. rot[r].l = max(arr[i].w, arr[i].h);
  29. rot[r].w = min(arr[i].w, arr[i].h);
  30. r++;
  31.  
  32. rot[r].h = arr[i].w;
  33. rot[r].l = max(arr[i].l, arr[i].h);
  34. rot[r].w = min(arr[i].l, arr[i].h);
  35. r++;
  36. }
  37.  
  38. n = 3*n;
  39. qsort(rot, n, sizeof(rot[0]), compare);
  40.  
  41. int tab[n];
  42. int res[n];
  43.  
  44. for(int i=0; i<n; i++)
  45. tab[i] = rot[i].h, res[i] = -1;
  46.  
  47. for(int i=1; i<n; i++)
  48. {
  49. for(int j=0; j<i; j++)
  50. {
  51. if(rot[i].l < rot[j].l && rot[i].w < rot[j].w && tab[j] + rot[i].h > tab[i])
  52. {
  53. tab[i] = tab[j] + rot[i].h;
  54. res[i] = j;
  55. }
  56. }
  57. }
  58.  
  59. int k=n-1;
  60. while(k != -1)
  61. {
  62. printf("%2d x %2d x %2d\n", rot[k].l, rot[k].w, rot[k].h);
  63. k = res[k];
  64. }
  65.  
  66. return tab[n-1];
  67. }
  68.  
  69. int main()
  70. {
  71. Box arr[] = { {7, 6, 4}, {3, 2, 1}, {6, 5, 4}, {32, 12, 10} };
  72. int n = sizeof(arr)/sizeof(arr[0]);
  73.  
  74. printf("\nMax Box(Stack) Height: %d\n", maxBoxHeight(arr, n));
  75.  
  76. return 0;
  77. }
  78.  
Success #stdin #stdout 0s 3140KB
stdin
Standard input is empty
stdout
 2 x  1 x  3
 3 x  2 x  1
 5 x  4 x  6
 6 x  5 x  4
 7 x  6 x  4
12 x 10 x 32
32 x 12 x 10

Max Box(Stack) Height: 60