ARTICLE · 1366929
别背模板!从暴力枚举到一维 DP 的“神仙顿悟”
GESP六级真题《条形蛋糕》解析:别背模板!从暴力枚举到一维 DP 的“神仙顿悟”
作者:编程徐老师
公众号:少儿编程指南
在近期的 GESP 202606 六级考试中,P17012《条形蛋糕》 这道题让很多同学在考场上皱起了眉头。
为什么?因为一看到“把整块蛋糕切成不同组合,求最大利润”,很多同学的第一反应就是:这题好复杂,是不是要用二维的“区间 DP”去推导?结果越想越绕,代码根本写不出来。
但实际上,有一位同学在考场上用最笨的方法——把所有情况都枚举了一遍,最后竟然自己总结出了极简的 “一维 DP” 解法!
今天,徐老师就结合最新录制的 【视频精讲】 ,带大家复盘这个极其精彩的思维推导过程。
🚨 痛点:为什么贪心会死,区间 DP 会绕?
遇到这道题,很多同学的思维误区有两个:
1. 贪心误区:每次都切下单价最贵的那一块。但局部最优不等于全局最优,剩下拼凑不出来的边角料会让你血本无归。 2. 区间 DP 误区:上来就定义 dp[i][j]表示区间[i, j]的最大利润。结果推导状态转移方程时,把自己绕晕了,代码写得又长又容易错。
💡 破局:从“暴力枚举”中走出的光明大道
其实,这道题有一个极其关键的特征:无论你在哪里切,剩下的蛋糕依然是一段独立的、可以继续切的长条。
这位同学的做法非常聪明,他没有死记硬背高级算法,而是拿笔在纸上开始 “暴力枚举”:
• 长度为 1 的蛋糕,怎么切最赚? • 长度为 2 的蛋糕,是直接卖划算,还是切成 1+1划算?• 长度为 3 的蛋糕,是直接卖划算,还是切成 1+2或2+1划算?• ……
枚举到长度为 4 或 5 的时候,规律出现了!他发现,我们根本不需要关心这根蛋糕具体在什么位置,只需要关心它的“总长度”就可以了!
🚀 顿悟:极简的一维 DP
顺着枚举的规律,可以直接把一个二维的复杂问题,降维打击成一维 DP。
状态定义极其简单:
定义 dp[i] 表示:长度为 i 的蛋糕,能获得的最大利润。
状态转移方程(就是你枚举出来的规律):
面对一根长度为 i 的蛋糕,我们枚举第一刀切下来的长度 j(1 <= j <= i):
当前的最大利润 = 直接卖的价格,切下长度为 的价格 + 剩余长度为 的最大利润
核心代码其实只有短短几行(伪代码):
for (int i = 1; i <= n; i++) { // 枚举蛋糕的总长度
for (int j = 1; j <= i; j++) { // 枚举第一刀切多长
dp[i] = max(dp[i], price[j] + dp[i - j]);
}
}为什么它能行?
因为切下来的部分互不影响,长度为 i 的最大利润,完全可以从长度为 i-j 的最大利润推导出来。没有后效性,完美契合 DP 的核心思想。
🧠 徐老师总结:算法竞赛的终极真相
很多同学觉得 DP 很难,是因为他们一上来就试图去背诵“状态转移方程”。但真正的算法高手都知道一个秘密:暴力枚举是动态规划之母。
当你面对一个不知道如何下手的 DP 题时,不妨像这位同学一样,在草稿纸上老老实实把 的所有情况都列出来。写着写着,当你发现“大问题都是由小问题拼凑而成”的那一刻,规律就自然浮现了。
一维还是二维,不是背出来的,是通过枚举推导出来的!
👇 福利
无论孩子是刚接触 C++ 的“零基础小白”,还是正在备战下一届 CSP 的“刷题党”,都欢迎各位老师、家长、学生在评论区留言。
我们一起交流探讨,复盘今年的经验,为下一年的学习与备赛计划做充分的准备!期待听到你们的声音。👇















































































