江门免费模板建站,公司网站建设深圳,八爪鱼 导入 wordpress,临沂做网站价格题目#xff1a;
给你一堆n个箱子#xff0c;箱子宽 wi、深 di、高 hi。箱子不能翻转#xff0c;将箱子堆起来时#xff0c;下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法#xff0c;搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组…题目
给你一堆n个箱子箱子宽 wi、深 di、高 hi。箱子不能翻转将箱子堆起来时下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。
输入使用数组[wi, di, hi]表示每个箱子。 示例 输入box [[1, 1, 1], [2, 2, 2], [3, 3, 3]] 输出6 输入box [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]] 输出10 解题思路
1.先对数组进行排序我们按照箱子的第一个值宽来进行升序排序这里为什么不用高呢因为尽管我们需要计算的是最大高度但最终堆箱子需要宽、深、高都小于下面的箱子所以直接按宽来排序
2.用dp[i]记录以第i个箱子结尾的箱堆的最大高度
3.返回dp[n] 源代码如下
class Solution {
public:int pileBox(vectorvectorint box) {//先按箱子的宽wi 进行升序排序sort(box.begin(),box.end(),[](const vectorint a,const vectorint b){return a[0]b[0];});//计算有多少个箱子int nbox.size();vectorint dp(n,0);//dp[i]表示以第i个箱子结尾的最高箱子高度//起始的高度就是第一个箱子的高度dp[0]box[0][2];//ans记录答案int ansdp[0];//从第二个箱子开始找最大高度的箱子堆for(int i1;in;i){//每找一次 都要讲当前最大高度置为0int max_hi0;//找第i个箱子之前的其他箱子组成箱子堆for(int j0;ji;j){//符合条件长宽高都小于下面的箱子才能堆到上面if(box[j][0]box[i][0]box[j][1]box[i][1]box[j][2]box[i][2]){//当前最大高度max_himax(max_hi,dp[j]);}//dp[i]就等于当前最大高度当前箱子的高度dp[i]max_hibox[i][2];//更新答案的最大值ansmax(ans,dp[i]);}}//返回答案return ans;}
};
