# 【GESP】C++六级真题 luogu-P17012, [GESP202606 六级] 条形蛋糕

> Author: OneCoder (李宏哲) | Canonical: https://www.coderli.com/gesp-6-luogu-p17012/
> Published: 2026-07-09 | Topic: GESP C++ 编程考级 / 六级
> Tags: GESP, C++, 算法, 动态规划, DP

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

```plaintext
4
1 5 8 9
```

##### 输出 #1

```plaintext
10
```

#### 输入输出样例 #2

##### 输入 #2

```plaintext
10
1 5 8 9 10 17 17 20 24 30
```

##### 输出 #2

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

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

---

---
Source: OneCoder (https://www.coderli.com/gesp-6-luogu-p17012/) | GESP Wiki: https://wiki.coderli.com/ | OI-Game: https://oi.coderli.com/
