

463 / 3709,前 12.5%

1240 / 9290,前13.3%
给你 n 个长方体 cuboids ,其中第 i 个长方体的长宽高表示为 cuboids[i] = [widthi, lengthi, heighti](下标从 0 开始)。请你从 cuboids 选出一个 子集 ,并将它们堆叠起来。
如果 widthi <= widthj 且 lengthi <= lengthj 且 heighti <= heightj ,你就可以将长方体 i 堆叠在长方体 j 上。你可以通过旋转把长方体的长宽高重新排列,以将它放在另一个长方体上。
返回 堆叠长方体 cuboids 可以得到的 最大高度 。
示例 1:

输入:cuboids = [[50,45,20],[95,37,53],[45,23,12]]
输出:190
解释:
第 1 个长方体放在底部,53x37 的一面朝下,高度为 95 。
第 0 个长方体放在中间,45x20 的一面朝下,高度为 50 。
第 2 个长方体放在上面,23x12 的一面朝下,高度为 45 。
总高度是 95 + 50 + 45 = 190 。
示例 2:
输入:cuboids = [[38,25,45],[76,35,3]]
输出:76
解释:
无法将任何长方体放在另一个上面。
选择第 1 个长方体然后旋转它,使 35x3 的一面朝下,其高度为 76 。
示例 3:
输入:cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]
输出:102
解释:
重新排列长方体后,可以看到所有长方体的尺寸都相同。
你可以把 11x7 的一面朝下,这样它们的高度就是 17 。
堆叠长方体的最大高度为 6 * 17 = 102 。
提示:
n == cuboids.length
1 <= n <= 100
1 <= widthi, lengthi, heighti <= 100来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-height-by-stacking-cuboids 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int maxHeight(vector<vector<int>>& cub) {
sort(cub.begin(), cub.end(),[&](auto& a, auto& b){
return a[0]+a[1]+a[2] < b[0]+b[1]+b[2];
});
int n = cub.size();
vector<vector<vector<int>>> dp(101,vector<vector<int>>(101, vector<int>(101, -1)));
dp[0][0][0] = 0;
dp[cub[0][0]][cub[0][1]][cub[0][2]] = max(dp[cub[0][0]][cub[0][1]][cub[0][2]],cub[0][2]);
dp[cub[0][0]][cub[0][2]][cub[0][1]] = max(dp[cub[0][0]][cub[0][2]][cub[0][1]],cub[0][1]);
dp[cub[0][1]][cub[0][0]][cub[0][2]] = max(dp[cub[0][1]][cub[0][0]][cub[0][2]],cub[0][2]);
dp[cub[0][2]][cub[0][0]][cub[0][1]] = max(dp[cub[0][2]][cub[0][0]][cub[0][1]],cub[0][1]);
dp[cub[0][1]][cub[0][2]][cub[0][0]] = max(dp[cub[0][1]][cub[0][2]][cub[0][0]],cub[0][0]);
dp[cub[0][2]][cub[0][1]][cub[0][0]] = max(dp[cub[0][2]][cub[0][1]][cub[0][0]],cub[0][0]);
for(int i = 1; i < n; ++i)
{
vector<vector<vector<int>>> temp(dp.begin(), dp.end());
int a = cub[i][0], b = cub[i][1], c = cub[i][2];
for(int w = 0; w <= 100; ++w)
{
for(int l = 0; l <= 100; ++l)
{
for(int h = 0; h <= 100; ++h)
{
if(temp[w][l][h] == -1)
continue;
if(a >= w && b >= l && c >= h)
temp[a][b][c] = max(temp[a][b][c], dp[w][l][h]+c);
if(b >= w && a >= l && c >= h)
temp[b][a][c] = max(temp[b][a][c], dp[w][l][h]+c);
if(a >= w && c >= l&& b >= h)
temp[a][c][b] = max(temp[a][c][b], dp[w][l][h]+b);
if(c >= w && a >= l&& b >= h)
temp[c][a][b] = max(temp[c][a][b], dp[w][l][h]+b);
if(b >= w && c >=l&& a >= h)
temp[b][c][a] = max(temp[b][c][a], dp[w][l][h]+a);
if(c >= w && b >=l&& a >= h)
temp[c][b][a] = max(temp[c][b][a], dp[w][l][h]+a);
}
}
}
dp = temp;
}
int ans = 0;
for(int h = 1; h <= 100; h++)
for(int w = 1; w <= 100; ++w)
{
for(int l = 1; l <= 100; ++l)
{
ans = max(ans, dp[w][l][h]);
}
}
return ans;
}
};class Solution {
public:
int maxHeight(vector<vector<int>>& cub) {
vector<vector<int>> C(6, vector<int>(3));
C[0] = {0,1,2};
C[1] = {0,2,1};
C[2] = {1,0,2};
C[3] = {1,2,0};
C[4] = {2,0,1};
C[5] = {2,1,0};//最后一维是高度维
for(auto& c : cub)
sort(c.begin(), c.end());
sort(cub.begin(), cub.end());
int n = cub.size();
vector<vector<int>> dp(n, vector<int>(6, 0));
dp[0][0] = cub[0][C[0][2]];
dp[0][1] = cub[0][C[1][2]];
dp[0][2] = cub[0][C[2][2]];
dp[0][3] = cub[0][C[3][2]];
dp[0][4] = cub[0][C[4][2]];
dp[0][5] = cub[0][C[5][2]];
for(int i = 1; i < n; ++i)
{
for(int c1 = 0; c1 < 6; ++c1)
{
dp[i][c1] = cub[i][C[c1][2]];//初始化为自己的高度
for(int j = 0; j < i; ++j)
{
for(int c2 = 0; c2 < 6; ++c2)
{
if(cub[j][C[c2][0]] <= cub[i][C[c1][0]]
&& cub[j][C[c2][1]] <= cub[i][C[c1][1]]
&& cub[j][C[c2][2]] <= cub[i][C[c1][2]])
{
dp[i][c1] = max(dp[i][c1], dp[j][c2]+cub[i][C[c1][2]]);
}
}
}
}
}
int ans = 0;
for(int i = 0; i < n; i++)
{
for(int k = 0; k < 6; k++)
{
ans = max(ans, dp[i][k]);
}
}
return ans;
}
};332 ms 9.8 MB C++