2026年6月GESP真题及题解（C++六级）：条形蛋糕

题目描述

寒假到了，小杨同学打算找一份兼职，顺便体验一下打工人的生活。

小杨同学给一家蛋糕店发送了一份自己的简历，希望可以在寒假来这里帮忙。店长最近正好遇到了一个难题：店里每天会做一条长条蛋糕，但是不同长度的蛋糕块卖出的价格不同，应该怎么分才能卖得最多呢？

有趣的是店长曾经学习过计算机专业。他最近对动态规划算法很感兴趣，于是打算用这个问题考一考小杨同学，问题如下：

• 给定一条长度为 $n$ 的长条蛋糕和一个价格表，该价格表表示长度为 $i$ ($i=1,2,\dots ,n$) 的蛋糕块的价格为 $p_i$。求蛋糕的分割方案，使得总销售价格最大，注意蛋糕块的长度必须为整数。

输入格式

第一行一个正整数 $n$ ($1\le n\le 10^3$)，表示长条蛋糕的总长度。

第二行 $n$ 个正整数 $p_1,p_2,\dots ,p_n$ ($1\le p_i\le 10^5$)，表示不同长度蛋糕块的价格。

输出格式

一行一个正整数，表示最大总销售价格。

输入输出样例 1

输入 1

4
1 5 8 9

输出 1

10

输入输出样例 2

输入 2

10
1 5 8 9 10 17 17 20 24 30

输出 2

30

说明/提示

样例解释

第一个样例中，长度为 $1$ 的蛋糕价值为 $1$，长度为 $2$ 的蛋糕价值为 $5$，长度为 $3$ 的蛋糕价值为 $8$，长度为 $4$ 的蛋糕价值为 $9$；

总长度为 $4$ 的长条蛋糕，有 { 4 } , { 1 , 3 } , { 2 , 2 } , { 1 , 1 , 2 } , { 1 , 1 , 1 , 1 } \{4\}, \{1, 3\}, \{2, 2\}, \{1, 1, 2\}, \{1, 1, 1, 1\} {4},{1,3},{2,2},{1,1,2},{1,1,1,1} 五种本质不同的分法。

其对应的总销售价格分别为 $9,9,10,7,4$，故最大总销售价格为 $10$。

第二个样例中，长度为 $10$ 的长条蛋糕，销售价格最大的分法为 { 10 } \{10\} {10}，最大总销售价格为 $30$。

---

思路分析

本题是经典的“钢条切割”问题，可用动态规划求解。
设 dp[i] 表示长度为 i 的长条蛋糕能获得的最大总价格。

对于长度 i，我们考虑第一段切下的长度 j（1 ≤ j ≤ i），则该段的收益为 p[j]，剩余部分长度为 i-j，其最大收益为 dp[i-j]，故总收益为 p[j] + dp[i-j]。
枚举所有可能的 j，取最大值即为 dp[i]。

状态转移方程：

dp[i] = max{ p[j] + dp[i-j]  |  1 ≤ j ≤ i }

初始条件：dp[0] = 0（长度为0时收益为0）。

最终答案即为 dp[n]。
时间复杂度 O(n²)，空间复杂度 O(n)。

---

代码实现

#include <bits/stdc++.h> 
using namespace std;

long long p[1010], dp[1010]; // p：价格表，dp：最大收益

int main() {
    int n;
    cin >> n; 
    for (int i = 1; i <= n; i++) cin >> p[i]; 
    
    dp[0] = 0; //长度0收益为0
    for (int i = 1; i <= n; i++) { //计算dp[1]到dp[n]
        dp[i] = p[i]; //先假设不切，整块卖出
        for (int j = 1; j < i; j++) { //枚举第一段长度j（j从1到i-1）
            dp[i] = max(dp[i], p[j] + dp[i - j]); //尝试切成长度j和剩余部分
        }
    }
    cout << dp[n]; //输出最大总价格
    return 0;
}

---

功能分析

• 输入：一个整数 n 和 n 个正整数 p₁, p₂, …, pₙ，分别代表蛋糕总长度和各长度蛋糕块的价格。
• 处理：使用动态规划自底向上计算每个长度 i 的最大收益，通过枚举第一段长度 j，比较切分与不切分的收益，最终得到长度为 n 的最优值。
• 输出：一个正整数，表示最大总销售价格。
• 正确性：状态转移覆盖所有可能的切分方案，且无后效性，故能保证最优解。
• 效率：O(n²) 时间复杂度，对于 n=1000 完全可行。

---

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
	cout<<"##########  一站式掌握信奥赛知识!  ##########";
	cout<<"#############  冲刺信奥赛拿奖!  #############";
	cout<<"######  课程购买后永久学习，不受限制!   ######";
	return 0;
}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
	cout<<"跟着王老师一起学习信奥赛C++";
	cout<<"    成就更好的自己！       ";
	cout<<"  csp信奥赛一等奖属于你!   ";
	return 0;
}