DP #4 Box Stacking Problem

DP #4: Box Stacking Problem

Problem Statement: here

Solution : 

A box can be placed on top of another only if both it’s base dimensions width and depth are less than a box on which it stacked on. There is no restriction on height, a tall box can be placed on a short box.

The point is that we can rotate the box, and change the (l,b,h) configuration and we can treat each box as 3 different boxes because we can use multiple instances of the given box. 

Another constraint is that we can place a box on top of another box only if the width of the top box < width of the bottom box and similarly for depth. So, we first need to construct 3*n boxes and then sort them on the basis of the base area and apply LIS for height. 

Implementation: 

int Solution::solve(vector<vector<int> > &A) { int n = A.size(); vector<pair<int,pair<int,int>>> v; for(int i = 0; i< n; i++){ int l,b,h; l = A[i][0]; b = A[i][1]; h = A[i][2]; v.push_back({l,{max(b,h),min(b,h)}}); v.push_back({b,{max(l,h),min(l,h)}}); v.push_back({h,{max(b,l),min(b,l)}}); } sort(begin(v),end(v),[](pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){ return ((long long int)a.second.first*(long long int)a.second.second) >=

((long long int)b.second.first*(long long int)b.second.second); }); int dp[3*n + 5]; int mxheight = -1; for(int i = 0; i< v.size(); i++){ dp[i] = v[i].first; for(int j = 0; j< i; j++){ if(v[j].second.first > v[i].second.first and v[j].second.second >

v[i].second.second){ dp[i] = max(dp[i],dp[j]+v[i].first); } } mxheight = max(mxheight, dp[i]); } return mxheight; }

Try next : https://leetcode.com/problems/russian-doll-envelopes/

I will post solution to this question later on!