【GESP】C++六级真题 luogu-P17012, [GESP202606 六级] 条形蛋糕
GESP C++六级2026年6月真题。本题是经典的「切割问题」（Rod Cutting Problem），考察一维动态规划。给定一条长度为 $n$ 的蛋糕和各长度的价格表，求最优分割方案使总售价最大。难度⭐⭐。本题在洛谷评定为普及-。
P17012 [GESP202606 六级] 条形蛋糕
题目要求
题目描述
给定一条长度为 $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
1
2
4
1 5 8 9
输出 #1
1
10
输入输出样例 #2
输入 #2
1
2
10
1 5 8 9 10 17 17 20 24 30
输出 #2
1
30
说明/提示
第一个样例中，长度为 $1$ 的蛋糕价值为 $1$，长度为 $2$ 的蛋糕价值为 $5$，长度为 $3$ 的蛋糕价值为 $8$，长度为 $4$ 的蛋糕价值为 $9$；
总长度为 $4$ 的长条蛋糕，有 ${4}, {1, 3}, {2, 2}, {1, 1, 2}, {1, 1, 1, 1}$ 五种本质不同的分法。
其对应的总销售价格分别为 $9, 9, 10, 7, 4$，故最大总销售价格为 $10$。
第二个样例中，长度为 $10$ 的长条蛋糕，销售价格最大的分法为 ${10}$，最大总销售价格为 $30$。
数据范围
$1 \le n \le 10^3$，$1 \le p_i \le 10^5$。
题目分析
本题是算法学习中非常经典的 切割问题（Rod Cutting Problem），也是动态规划入门的典型例题之一。核心思路是：对于一段长度为 $n$ 的蛋糕，枚举第一刀切下的长度 $j$（$1 \le j \le n$），取「长度为 $j$ 的蛋糕售价」+「剩余长度 $n - j$ 的最优售价」的最大值。
1. 状态定义
定义 $dp[i]$ 为长度为 $i$ 的蛋糕，通过最优切割方案所能获得的最大总售价。
显然有边界条件：$dp[0] = 0$（长度为 $0$ 的蛋糕，售价为 $0$）。
2. 状态转移方程
对于长度为 $i$ 的蛋糕，我们枚举第一段切下来的长度 $j$（$1 \le j \le i$）：
- 切下长度为 $j$ 的一块，获得售价 $p_j$
- 剩余部分长度为 $i - j$，其最优售价为 $dp[i - j]$（已经计算好的子问题）
因此状态转移方程为：
\[dp[i] = \max_{1 \le j \le i}\{p_j + dp[i - j]\}\]最终答案为 $dp[n]$。
3. 直觉理解
可以这样理解这个递推过程：要把长度为 $i$ 的蛋糕卖出最高价，我们可以：
- 整块卖（$j = i$），获得 $p_i + dp[0] = p_i$
- 先切一块长度为 $1$ 的卖 $p_1$，剩下长度 $i - 1$ 按最优方案卖，获得 $p_1 + dp[i-1]$
- 先切一块长度为 $2$ 的卖 $p_2$，剩下长度 $i - 2$ 按最优方案卖，获得 $p_2 + dp[i-2]$
- ……依此类推
取所有方案中的最大值，就是 $dp[i]$。
4. 样例验证
以样例 $1$ 为例，$n = 4$，价格表为 $p = [1, 5, 8, 9]$。
| 长度 $i$ | 枚举所有切法 | $dp[i]$ |
|---|---|---|
| $0$ | — | $0$ |
| $1$ | $p_1 + dp[0] = 1 + 0 = 1$ | $1$ |
| $2$ | $p_1 + dp[1] = 1 + 1 = 2$；$p_2 + dp[0] = 5 + 0 = 5$ | $5$ |
| $3$ | $p_1 + dp[2] = 1 + 5 = 6$；$p_2 + dp[1] = 5 + 1 = 6$；$p_3 + dp[0] = 8 + 0 = 8$ | $8$ |
| $4$ | $p_1 + dp[3] = 1 + 8 = 9$；$p_2 + dp[2] = 5 + 5 = \mathbf{10}$；$p_3 + dp[1] = 8 + 1 = 9$；$p_4 + dp[0] = 9 + 0 = 9$ | $10$ |
$dp[4] = 10$，对应切割方案为 ${2, 2}$，与样例输出一致。
5. 复杂度分析
- 时间复杂度：外层循环枚举蛋糕长度 $i$（$1$ 到 $n$），内层循环枚举第一刀位置 $j$（$1$ 到 $i$），总计算量为 $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$，即 $O(n^2)$。$n = 1000$ 时约 $500000$ 次运算，完全可以通过
- 空间复杂度：$dp$ 数组 $O(n)$，价格表 $O(n)$，总体 $O(n)$
6. 注意事项
- 最大总售价不会超过 $n \times \max(p_i) = 1000 \times 10^5 = 10^8$，
int类型足以存储 - 本题和经典的「完全背包」问题有相似之处：每种长度的蛋糕可以使用无限次（切出多段相同长度），但本题的建模更直接——直接枚举第一段的长度即可
- $dp[0] = 0$ 这个边界条件很关键，它表示长度为 $0$ 时无需切割，售价为 $0$
示例代码
枚举每个长度的最优切割方案，通过一维 DP 自底向上求解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
int main() {
int n;
std::cin >> n;
int p[1005]; // 价格表：p[i] 表示长度为 i 的蛋糕块的价格
int dp[1005]; // dp[i] 表示长度为 i 的蛋糕的最大总售价
// 读入各长度蛋糕块的价格
for (int i = 1; i <= n; i++) {
std::cin >> p[i];
}
dp[0] = 0; // 边界条件：长度为 0 的蛋糕，售价为 0
// 自底向上计算 dp[1], dp[2], ..., dp[n]
for (int i = 1; i <= n; i++) {
dp[i] = 0; // 初始化为 0，准备取最大值
// 枚举第一段切下来的长度 j（从 1 到 i）
for (int j = 1; j <= i; j++) {
// p[j] 是长度为 j 的蛋糕块的价格
// dp[i - j] 是剩余长度 i - j 的最大售价（已在前面计算好）
dp[i] = std::max(dp[i], p[j] + dp[i - j]);
}
}
// dp[n] 即为长度为 n 的蛋糕的最大总销售价格
std::cout << dp[n] << std::endl;
return 0;
}
拓展思考
本题本质上等价于一个完全背包问题：将蛋糕总长度 $n$ 视为背包容量，长度为 $j$ 的蛋糕块视为一种物品（重量为 $j$，价值为 $p_j$），每种物品可以无限使用，求恰好装满背包时的最大价值。两种建模方式的代码几乎相同，只是理解角度不同。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
"luogu-"系列题目可在洛谷题库进行在线评测。
"bcqm-"系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
