202606-条形蛋糕(luogu-P17012)

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

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\}$ 五种本质不同的分法。

其对应的总销售价格分别为 $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[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]$。

$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 自底向上求解。

#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$），每种物品可以无限使用，求恰好装满背包时的最大价值。两种建模方式的代码几乎相同，只是理解角度不同。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号