➤ Problem Link : BABTWR
👉 Hint : Solve LIS DP problem first. Think about different possible rotations to solve.
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
int main()
{
while(1)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
if(n==0)
break;
int ht[n],wd[n],dpt[n];
long long int sum=0;
for(int i=0;i<n;i++)
{
cin>>ht[i]>>wd[i]>>dpt[i];
sum+=ht[i]+wd[i]+dpt[i];
}
vector<pair<int,int > >base;
vector<int> h;
for(int i=0;i<n;i++)
{
base.push_back(make_pair(wd[i],dpt[i]));
h.push_back(ht[i]);
base.push_back(make_pair(wd[i],ht[i]));
h.push_back(dpt[i]);
base.push_back(make_pair(ht[i],dpt[i]));
h.push_back(wd[i]);
base.push_back(make_pair(ht[i],wd[i]));
h.push_back(dpt[i]);
base.push_back(make_pair(dpt[i],wd[i]));
h.push_back(ht[i]);
base.push_back(make_pair(dpt[i],ht[i]));
h.push_back(wd[i]);
}
bool dp[sum+1][h.size()+1];
memset(dp,true,sizeof(dp));
int height=0;
for(int i=1;i<=sum;i++)
{
for(int j=0;j<h.size();j++)
{
for(int k=0;k<h.size();k++)
{
if(i==h[j] || (i>=h[j] && dp[i-h[j]][k]==true && base[k].first<base[j].first && base[k].second<base[j].second))
{
dp[i][j]=true;
height=max(height,i);
break;
}
dp[i][j]=false;
}
}
}
cout<<height<<endl;
}
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.