💗博主介绍：计算机专业的一枚大学生 来自重庆 @燃于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>
using namespace std;
const int N = 410, M = 4e4 + 10;
int n;
struct node
{
int h, a, c;
}e[N];
//int f[N][M]; 优化一维
int f[M];
bool cmp(node& x, node& y)
{
return x.a < y.a;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> e[i].h >> e[i].a >> e[i].c;
sort(e + 1, e + 1 + n, cmp);
int ret = 0;
//多重背包
for(int i = 1; i <= n; i++)
{
int h = e[i].h, a = e[i].a, c = e[i].c;
for(int j = a; j >= 0; j—) //第二层循环逆序
{
for(int k = 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;
return 0;
}
2.语文成绩
题目： P2367 语文成绩
解法：差分
这道题就是一道差分的模板题目，不断维护（+ -）区间内的所有内容（学生成绩），然后用前缀和还原数组，一边还原，一边求最小值。 
代码：
#include <iostream>
using namespace std;
const int N = 5e6 + 10;
int n, p;
int f[N];
int main()
{
cin >> n >> p;
for(int i = 1; i <= n; i++) //差分数组
{
int x; cin >> x;
f[i] += x; f[i + 1] -= x;
}
while(p—) //维护差分数组
{
int x, y,z; cin >> x >> y >> z;
f[x] += z;
f[y + 1] -= z;
}
int ret = 1e9;
for(int i = 1; i <= n; i++) //前缀和还原数组
{
f[i] += f[i – 1];
ret = min(ret, f[i]);
}
cout << ret << endl;
return 0;
}
3.跳跳
题目： P4995 跳跳！
解法：贪心
先从小到大进行排序，每次都跳距离当前位置最远的位置（h差最大），左右跳，用双指针（下标）更新。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 310;
int n;
LL h[N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> h[i];
sort(h + 1, h + 1 + n);
int l = 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;
return 0;
}
4.数列分段 Section II
题目： P1182 数列分段 Section II
解法：二分答案
看到题目的关键词“最大值最小”，立马想到二分算法，并且也可以写出二段性：
当分的段数越多的时候，最大的和越小；
当分的段数越少的时候，最大的和越小。
因此，可以用二分答案来解决。
关于（计算） calc 函数，传入⼀个和 x，求出最少能分多少段：
从前往后累加，只要和小于 x，就⼀直加；（这里用long long，防溢出）
直到和超过 x，之前的为⼀段，然后从该位置继续累加。注意：最后要额外加一段（最后一段）。 
代码：
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL a[N];
int calc(LL x)
{
int cnt = 0, sum = 0;
for(int i = 1; i <= n; i++)
{
sum += a[i];
if(sum > x)
{
cnt++;
sum = a[i];
}
}
return cnt + 1; //划分后，最后还有一段
}
int main()
{
cin >> n >> m;
LL l = 0, r = 0;
for(int i = 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;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
5.修理牛棚
题目： P1209 [USACO1.3] 修理牛棚 Barn Repair
解法：正难则反 + 贪心
这道题既要求了木板数有限，有要求了木板长度最短，如果挨个考虑放置每个木板的话，非常复杂，用dfs暴搜会超时。那么，我们将问题转化（逆向思维）：先放一块长木板，考虑中间的间隔，m个木板，就有m – 1个间隔，（c头奶牛，最多间隔数c – 1）。用贪心：排序，优先考虑处理间隔较长的，这样用的木板总长度最短。 模板长度：a[c] – a[1] + 1。
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210;
int m, s, c;
int a[N]; //奶牛所占牛棚编号
int b[N]; //间隔
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
cin >> m >> s >> c;
for(int i = 1; i <= c; i++) cin >> a[i];
sort(a + 1, a + 1 + c);
for(int i = 1; i < c; i++)
{
b[i] = a[i + 1] – a[i] – 1;
}
sort(b + 1, b + 1 + c, cmp);
int ret = a[c] – a[1] + 1;
for(int i = 1; i < m && i < c; i++)
{
ret -= b[i];
}
cout << ret << endl;
return 0;
}
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>
using namespace std;
const int N = 110, M = 25010;
int n;
int a[N];
bool f[M];
int main()
{
int T; cin >> T;
while(T—)
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
memset(f, 0, sizeof f); //清空数据
f[0] = true;
int ret = 0;
for(int i = 1; i <= n; i++)
{
if(!f[a[i]]) ret++; //1~i-1不能凑出i,保留i
for(int j = a[i]; j <= a[n]; j++)
{
f[j] = f[j] || f[j – a[i]]; //用||一个满足即可
}
}
cout << ret << endl;
}
return 0;
}
加油！志同道合的人会看到同一片风景。 看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！
