本文涉及知识点

C++贪心

LeetCode1691. 堆叠长方体的最大高度

给你 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

贪心

如果v1在v2的上面，则：
一，v2的最大值一定大于等于v1的三个值。
二，v2的次大值一定大于等于v1的两个值。
三，v2的最小值一定大于等于v1的最小值。
$⟺$ v1和v2 降序排序后,v1[i] <=v2[i]。
将cub数组排序。
for i = 1 to n-1 for j= 0 to i-1
如果v[j][1] <= v[i][1] 且v[j][2] <= v[i][2]。 MaxSelf(ans[i],ans[j]+cub[i][0])
cnt的初始值全为1。
如果v1能在v2上面，v1[0]或v1[1]或v1[2]做高都符合题意，而v1[0]最优。v1和v2同时旋转。

代码

核心代码

class Solution {
		public:
			int maxHeight(vector<vector<int>>& cuboids) {
				const int N = cuboids.size();
				for (auto& v : cuboids) {
					sort(v.begin(), v.end(), greater<>());
				}
				sort(cuboids.begin(), cuboids.end());
				vector<int> ans(N);
				for (int i = 0; i < N; i++) {
					int iMax = 0;
					for (int j = 0; j < i; j++) {
						if (cuboids[i][1] < cuboids[j][1]) { continue; }
						if (cuboids[i][2] < cuboids[j][2]) { continue; }
						iMax = max(iMax, ans[j]);
					}
					ans[i] = iMax + cuboids[i][0];
				}
				return *max_element(ans.begin(), ans.end());
			}
		};

单元测试

	vector<vector<int>> cuboids;
		TEST_METHOD(TestMethod11)
		{
			cuboids = { {50,45,20},{95,37,53},{45,23,12} };
			auto res = Solution().maxHeight(cuboids);
			AssertEx(190, res);
		}
		TEST_METHOD(TestMethod12)
		{
			cuboids = { {38,25,45},{76,35,3} };
			auto res = Solution().maxHeight(cuboids);
			AssertEx(76, res);
		}
		TEST_METHOD(TestMethod13)
		{
			cuboids = { {7,11,17},{7,17,11},{11,7,17},{11,17,7},{17,7,11},{17,11,7} };
			auto res = Solution().maxHeight(cuboids);
			AssertEx(102, res);
		}