💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于AC之乐✌专注于C++技术栈，算法，竞赛领域，技术学习和项目实战✌💗
💗根据博主的学习进度更新（可能不及时）
💗后续更新主要内容：C语言，数据结构，C++、linux（系统编程和网络编程）、MySQL、Redis、QT、Python、Git、爬虫、数据可视化、小程序、AI大模型接入，C++实战项目与学习分享。
👇🏻 精彩专栏 推荐订阅👇🏻
点击进入🌌作者专栏🌌：
Linux系统编程✅
算法画解✅
C++✅
🌟算法相关题目点击即可进入实操🌟
感兴趣的可以先收藏起来，请多多支持，还有大家有相关问题都可以给我留言咨询，希望希望共同交流心得，一起进步，你我陪伴，学习路上不孤单！
文章目录
- 前言
- 题目清单
- 1.Space Elevator 太空电梯
- 2.语文成绩
- 3.跳跳
- 4.数列分段 Section II
- 5.修理牛棚
- 6.货币系统
前言
这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。
对应题目点链接即可做。
本期涉及算法：贪心 + 动态规划（多重背包），差分，贪心，二分答案，正难则反 + 贪心，完全背包（动态规划）。
题目清单
1.Space Elevator 太空电梯
题目：P6771 [USACO05MAR] Space Elevator 太空电梯
解法：贪心 + 动态规划（多重背包）
贪心：当我们从前往后考虑每⼀个方块的时候，限定高度a[i]小的应该优先考虑。因为如果先放限定高度大的，这些限定高度小的就没法放了。因此，先对所有的方块按照限定高度a[i]从小到大排序。
接下来的问题就是挑⼀些方块出来，在不超过每⼀种方块的限定⾼度下，看看能堆成的最大高度是多
少。正好是多重背包问题。
1.状态表示：
f[i] [j]表示：从前i个方块中挑选，总⾼度不超过j的情况下，最大的高度是多少。
结果：整个f表中的最大值，就是我们要的结果。这里要注意，并不是 f[n] [m]，因为有可能考
虑不到第n个方块根本考虑不进去，最后一行根本就不会更新。
2.状态转移方程：
根据第i个方块选的数量，可以分成c[i] + 1种情况，要的是所有情况的最大值。设选了k个
方块，那么最大高度为f[i - 1] [j - k * h[i]] + k * h[i] 。
注意限定条件，循环⾼度的时候不能超过a[i] ，并且j - k * h >= 0 。
3.初始化：
取max,全部初始化为0。
4.填表顺序：
从左到右，空间优化（第二层循环：（逆序）从大到小）
代码：
#include<iostream>#include<algorithm>usingnamespacestd;constintN=410,M=4e4+10;intn;structnode{inth,a,c;}e[N];//int f[N][M]; 优化一维intf[M];boolcmp(node&x,node&y){returnx.a<y.a;}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>e[i].h>>e[i].a>>e[i].c;sort(e+1,e+1+n,cmp);intret=0;//多重背包for(inti=1;i<=n;i++){inth=e[i].h,a=e[i].a,c=e[i].c;for(intj=a;j>=0;j--)//第二层循环逆序{for(intk=0;k<=c&&k*h<=j;k++){f[j]=max(f[j],f[j-k*h]+k*h);}ret=max(ret,f[j]);}}cout<<ret<<endl;return0;}2.语文成绩
题目：P2367 语文成绩
解法：差分
这道题就是一道差分的模板题目，不断维护（+ -）区间内的所有内容（学生成绩），然后用前缀和还原数组，一边还原，一边求最小值。
代码：
#include<iostream>usingnamespacestd;constintN=5e6+10;intn,p;intf[N];intmain(){cin>>n>>p;for(inti=1;i<=n;i++)//差分数组{intx;cin>>x;f[i]+=x;f[i+1]-=x;}while(p--)//维护差分数组{intx,y,z;cin>>x>>y>>z;f[x]+=z;f[y+1]-=z;}intret=1e9;for(inti=1;i<=n;i++)//前缀和还原数组{f[i]+=f[i-1];ret=min(ret,f[i]);}cout<<ret<<endl;return0;}3.跳跳
题目：P4995 跳跳！
解法：贪心
先从小到大进行排序，每次都跳距离当前位置最远的位置（h差最大），左右跳，用双指针（下标）更新。
代码：
#include<iostream>#include<algorithm>usingnamespacestd;typedeflonglongLL;constintN=310;intn;LL h[N];intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>h[i];sort(h+1,h+1+n);intl=0,r=n;LL sum=0;while(l<r){sum+=(h[l]-h[r])*(h[l]-h[r]);l++;sum+=(h[l]-h[r])*(h[l]-h[r]);r--;}cout<<sum<<endl;return0;}4.数列分段 Section II
题目：P1182 数列分段 Section II
解法：二分答案
看到题目的关键词“最大值最小”，立马想到二分算法，并且也可以写出二段性：
当分的段数越多的时候，最大的和越小；
当分的段数越少的时候，最大的和越小。
因此，可以用二分答案来解决。
关于（计算） calc 函数，传入⼀个和 x，求出最少能分多少段：
从前往后累加，只要和小于 x，就⼀直加；（这里用long long，防溢出）
直到和超过 x，之前的为⼀段，然后从该位置继续累加。注意：最后要额外加一段（最后一段）。
代码：
#include<iostream>usingnamespacestd;typedeflonglongLL;constintN=1e5+10;intn,m;LL a[N];intcalc(LL x){intcnt=0,sum=0;for(inti=1;i<=n;i++){sum+=a[i];if(sum>x){cnt++;sum=a[i];}}returncnt+1;//划分后，最后还有一段}intmain(){cin>>n>>m;LL l=0,r=0;for(inti=1;i<=n;i++){cin>>a[i];l=max(l,a[i]);r+=a[i];}while(l<r){LL mid=(l+r)/2;if(calc(mid)<=m)r=mid;elsel=mid+1;}cout<<l<<endl;return0;}5.修理牛棚
题目：P1209 [USACO1.3] 修理牛棚 Barn Repair
解法：正难则反 + 贪心
这道题既要求了木板数有限，有要求了木板长度最短，如果挨个考虑放置每个木板的话，非常复杂，用dfs暴搜会超时。那么，我们将问题转化（逆向思维）：先放一块长木板，考虑中间的间隔，m个木板，就有m - 1个间隔，（c头奶牛，最多间隔数c - 1）。用贪心：排序，优先考虑处理间隔较长的，这样用的木板总长度最短。 模板长度：a[c] - a[1] + 1。
代码：
#include<iostream>#include<algorithm>usingnamespacestd;constintN=210;intm,s,c;inta[N];//奶牛所占牛棚编号intb[N];//间隔boolcmp(inta,intb){returna>b;}intmain(){cin>>m>>s>>c;for(inti=1;i<=c;i++)cin>>a[i];sort(a+1,a+1+c);for(inti=1;i<c;i++){b[i]=a[i+1]-a[i]-1;}sort(b+1,b+1+c,cmp);intret=a[c]-a[1]+1;for(inti=1;i<m&&i<c;i++){ret-=b[i];}cout<<ret<<endl;return0;}6.货币系统
题目：P5020 [NOIP 2018 提高组] 货币系统
解法：完全背包（动态规划）
由题目“无穷多张”，可以想到用完全背包解题。
题意：就是在一堆数中选几个数能够表示其他所有的数（货币表示问题），选出最少的数组个数。
性质：1.由于较大的数只能较小的数（<=）表示，那么可以先对所有的数升序排序；2.如果一个数i能被[i, i - 1]区间内的数表示，就可以舍去，如果不能，就保留。
于是，先排序，这道题目就转化为完全背包问题：
1.状态表式：bool f[i] [j]从前i个纸币挑选，能否凑成总和为j;
2.**状态转移方程：**f[i] [j] ：1.不选，f[i - 1] [j]; 2.选， f[i] [j - a[i]] 用||(二者满足其一即可)；
3.**初始化：**f[0] [0] = true，方便用于后面更新正确；
4.**填表顺序：**第二层（for循环），完全背包，从小到大；
5.**结果确定：**因为更新到这个数i之后，i一定能被本身表示，所以后面i一定会变为true，一边循环，一边更新结果（在第二层开始之前，第一层），如果f[a[i]] == 0, 就是还不能被表示出来，结果+1。
多组数据测试，每次要清空。
代码：
#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=110,M=25010;intn;inta[N];boolf[M];intmain(){intT;cin>>T;while(T--){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);memset(f,0,sizeoff);//清空数据f[0]=true;intret=0;for(inti=1;i<=n;i++){if(!f[a[i]])ret++;//1~i-1不能凑出i,保留ifor(intj=a[i];j<=a[n];j++){f[j]=f[j]||f[j-a[i]];//用||一个满足即可}}cout<<ret<<endl;}return0;}加油！志同道合的人会看到同一片风景。
看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！
