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

所属专题GESP 六级
题号标识P17012
代码 / 阅读C++11 · 10 min
累计阅读实时统计
TL;DR · 核心摘要

GESP C++六级2026年6月真题。本题是经典的「切割问题」(Rod Cutting Problem),考察一维动态规划。给定一条长度为 n 的蛋糕和各长度的价格表,求最优分割方案使总售价最大。难度⭐⭐。本题在洛谷评定为普及-。

GESP C++六级2026年6月真题。本题是经典的「切割问题」(Rod Cutting Problem),考察一维动态规划。给定一条长度为 的蛋糕和各长度的价格表,求最优分割方案使总售价最大。难度⭐⭐。本题在洛谷评定为普及-。

P17012 [GESP202606 六级] 条形蛋糕

题目要求

题目描述

给定一条长度为 的长条蛋糕和一个价格表,该价格表表示长度为 () 的蛋糕块的价格为 。求蛋糕的分割方案,使得总销售价格最大,注意蛋糕块的长度必须为整数。

输入格式

第一行一个正整数 (),表示长条蛋糕的总长度。

第二行 个正整数 (),表示不同长度蛋糕块的价格。

输出格式

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

输入输出样例 #1

输入 #1
PLAINTEXT· 2 行
4
1 5 8 9
输出 #1
PLAINTEXT· 1 行
10

输入输出样例 #2

输入 #2
PLAINTEXT· 2 行
10
1 5 8 9 10 17 17 20 24 30
输出 #2
PLAINTEXT· 1 行
30

说明/提示

第一个样例中,长度为 的蛋糕价值为 ,长度为 的蛋糕价值为 ,长度为 的蛋糕价值为 ,长度为 的蛋糕价值为 ;

总长度为 的长条蛋糕,有 五种本质不同的分法。

其对应的总销售价格分别为 ,故最大总销售价格为 。

第二个样例中,长度为 的长条蛋糕,销售价格最大的分法为 ,最大总销售价格为 。

数据范围

,。


题目分析

本题是算法学习中非常经典的 切割问题(Rod Cutting Problem),也是动态规划入门的典型例题之一。核心思路是:对于一段长度为 的蛋糕,枚举第一刀切下的长度 (),取「长度为 的蛋糕售价」+「剩余长度 的最优售价」的最大值。

1. 状态定义

定义 为长度为 的蛋糕,通过最优切割方案所能获得的最大总售价。

显然有边界条件:(长度为 的蛋糕,售价为 )。

2. 状态转移方程

对于长度为 的蛋糕,我们枚举第一段切下来的长度 ():

  • 切下长度为 的一块,获得售价
  • 剩余部分长度为 ,其最优售价为 (已经计算好的子问题)

因此状态转移方程为:

最终答案为 。

3. 直觉理解

可以这样理解这个递推过程:要把长度为 的蛋糕卖出最高价,我们可以:

  • 整块卖(),获得
  • 先切一块长度为 的卖 ,剩下长度 按最优方案卖,获得
  • 先切一块长度为 的卖 ,剩下长度 按最优方案卖,获得
  • ……依此类推

取所有方案中的最大值,就是 。

4. 样例验证

以样例 为例,,价格表为 。

长度 枚举所有切法
—
;
;;
;;;

,对应切割方案为 ,与样例输出一致。

5. 复杂度分析

  • 时间复杂度:外层循环枚举蛋糕长度 ( 到 ),内层循环枚举第一刀位置 ( 到 ),总计算量为 ,即 。 时约 次运算,完全可以通过
  • 空间复杂度: 数组 ,价格表 ,总体

6. 注意事项

  • 最大总售价不会超过 ,int 类型足以存储
  • 本题和经典的「完全背包」问题有相似之处:每种长度的蛋糕可以使用无限次(切出多段相同长度),但本题的建模更直接——直接枚举第一段的长度即可
  • 这个边界条件很关键,它表示长度为 时无需切割,售价为

示例代码

枚举每个长度的最优切割方案,通过一维 DP 自底向上求解。

C++· 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;
}

拓展思考

本题本质上等价于一个完全背包问题:将蛋糕总长度 视为背包容量,长度为 的蛋糕块视为一种物品(重量为 ,价值为 ),每种物品可以无限使用,求恰好装满背包时的最大价值。两种建模方式的代码几乎相同,只是理解角度不同。


OneCoder 信奥远征平台 · oi.coderli.com

看完题解,马上用 240 关实战检验掌握度

覆盖 GESP 1~8 级考纲心法、CSP-J 双栏阅读程序、错题动态变式推演与 90/120 分钟全真模考。

立即闯关
开源代码与考纲字典

配套题解代码归档于 yummy-code 仓库,完整知识点索引见 GESP Wiki。

技术交流与考级答疑

欢迎加入 C++ GESP/CSP 群(688906745) 或 Java/Python 群(982860385)。

同专栏相关推荐

OneCoder

OneCoder

始于 2012

持续记录 C++ GESP/CSP 信奥算法、Java 服务端架构与 Python 工程实战。官方唯一域名:coderli.com

读者讨论与留言

共 0 条讨论
邮箱仅用于接收回复通知,不对外展示
还没有读者留言,欢迎写下你的第一条交流笔记。