题解：AcWing 4548 猴子和香蕉

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：4548. 猴子和香蕉 - AcWing题库

【题目描述】

研究员正在测试猴子的智商。

他们将一串香蕉放到很高的地方，并给猴子一些积木。

如果猴子足够聪明，它应该能够通过将一个积木放到另一个积木上的方式，不断向上堆叠积木，建成一座高塔，并爬上去取得香蕉。

研究员一共给猴子提供了n nn种不同类型的积木，每种积木的供应数量无限多。

在堆叠过程中，猴子可以随意摆弄积木，自由决定积木的哪个面作为底面，以及积木的具体摆放朝向。

在堆叠时满足的条件是：位于下面的积木的长和宽必须严格大于位于上面的积木的长和宽。

堆叠的积木高度当然是越高越好，请你计算最大可能高度。

【输入】

输入包含多组测试数据。

每组数据第一行包含整数n nn。

接下来n nn行，每行包含三个整数x i , y i , z i x_i,y_i,z_ixi​,yi​,zi​，表示一种积木的长宽高。

当输入n = 0 n=0n=0时，输入结束。

【输出】

每组数据输出一行结果，格式为Case i: maximum height = x，其中i ii为组别编号（从1 11开始），x xx为最大可能高度。

【输入样例】

1 10 20 30 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 0

【输出样例】

Case 1: maximum height = 40 Case 2: maximum height = 21 Case 3: maximum height = 28 Case 4: maximum height = 342

【算法标签】

#线性DP-一维

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100;// 定义最大节点数intn;// 方块种类数量structNode{intL,W,H;// 方块的长、宽、高}a[N];// 方块数组intf[N];// DP数组，f[i]表示以第i个方块为顶时的最大高度// 比较函数：首先按L从大到小排序，L相同则按W从大到小排序boolcmp(Node x,Node y){if(x.L!=y.L)returnx.L>y.L;returnx.W>y.W;}// 添加方块函数：将长宽高信息存入方块结构体voidadd(inti,intl,intw,inth){a[i].L=l;a[i].W=w;a[i].H=h;}intmain(){intt=1;// 测试用例编号while(cin>>n,n)// 读入n，当n不为0时循环{for(inti=0;i<n;i++)// 处理每种原始方块{intl,w,h;cin>>l>>w>>h;// 读入原始方块的长宽高// 将每种方块转换为3种不同的放置方式add(3*i+1,max(l,w),min(l,w),h);// 以l,w为底，h为高add(3*i+2,max(l,h),min(l,h),w);// 以l,h为底，w为高add(3*i+3,max(w,h),min(w,h),l);// 以w,h为底，l为高}// 将所有方块按L从大到小排序，L相同则按W从大到小排序sort(a+1,a+n*3+1,cmp);f[1]=a[1].H;// 初始化DP数组，第一个方块的高度intans=f[1];// 初始化答案for(inti=2;i<=3*n;i++)// 遍历所有方块{intmaxn=0;// 记录可放置在当前方块下方的最大高度for(intj=1;j<i;j++)// 检查所有之前的方块{// 如果方块j的长和宽都大于方块i的长和宽，则方块j可以放在方块i下方if(a[j].L>a[i].L&&a[j].W>a[i].W){maxn=max(maxn,f[j]);// 更新最大高度}}f[i]=maxn+a[i].H;// 当前方块的高度加上下方最大高度ans=max(ans,f[i]);// 更新全局最大高度}cout<<"Case "<<t<<": maximum height = "<<ans<<endl;// 输出结果t++;// 测试用例编号加1}return0;}

【运行结果】

1 10 20 30 Case 1: maximum height = 40 2 6 8 10 5 5 5 7 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 Case 3: maximum height = 28 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 Case 4: maximum height = 342 0