第一幕蛋糕王国来了一个新店长1、暑假到了。蛋糕王国里新开了一家蛋糕店。每天早晨师傅都会做好一整条长长的蛋糕。1例如今天做了一条════════════════ 长度42店长问到底是整条卖最赚钱还是切成几块卖更赚钱于是小程序员们就被请来帮忙了。2、店长拿出了价格表1他说长度售价11元25元38元49元2也就是说长度1 █ 卖1元长度2 ██ 卖5元长度3 ███ 卖8元长度4 ████ 卖9元3店长说你可以随便切例如████ ↓ ██ ██或者████ ↓ █ ███或者████ ↓ █ █ █ █4目标只有一个赚钱最多 第二幕手工推演1、长度4。到底有哪些切法1第一种不切。████收入9元2第二种█ ███收入1893第三种██ ██收入5510哇已经超过9了4第四种███ █还是8195第五种█ █ █ █收入1111 46还有██ █ █收入511 7等等……7手工推演后最大108所以答案切成22最赚钱。这和样例完全一致。 第三幕如果长度变成100呢1、老师问如果蛋糕长度不是4。而是1002、你还能暴力枚举吗当然不能。怎么办动态规划登场。 第四幕DP的状态定义1、我们定义dp[i]表示长度为 i 的蛋糕最多能卖多少钱。2、例如dp[5]不是第五块蛋糕。而是长度5的蛋糕使用最棒的切法最多能赚多少钱。3、例如dp[3]8意思长度3无论怎么切最多赚8。 第五幕找规律1、现在老师问长度4怎么办不要急。先问最后一刀切多少2、第一种最后一块切1。那么前面还剩3于是收入等于dp[3] price[1]3、第二种最后切2。前面2收入dp[2] price[2]4、第三种最后切3。收入dp[1] price[3]5、第四种最后切4。收入dp[0] price[4]6、全部比较后。最大的max就是dp[4]7、于是规律出来了最后切1 ↓ dp[3]1最后切2 ↓ dp[2]5最后切3 ↓ dp[1]8最后切4 ↓ dp[0]9谁最大就是答案。 第六幕终于得到状态转移1、于是对于长度 i我们可以枚举最后一块长度 j那么剩下i-j已经算过。2、因此dp[i] max( dp[i], dp[i-j]price[j] )这就是我们的状态转移公式。 第七幕这道题是完全背包问题1、来看关键代码for(int i1;in;i) { for(int ji;jn;j) { dp[j]max(dp[j],dp[j-i]p[i]); } }2、外层i表示蛋糕长度。例如长度1 长度2 长度3 ……3、内层j表示当前正在计算的dp[j]4、计算 dp[j] 的顺序j 正序因为同一种长度可以切很多次例如面包长度1。可以1 1 1 .......无限使用。所以必须正序。这就是完全背包 第八幕参考代码#include iostream using namespace std; int dp[1010]; int price[1010]; int main() { int n; cin n; for(int i 1; i n; i) cin price[i]; // 枚举每一种蛋糕长度 for(int len 1; len n; len) { // 完全背包正序枚举 for(int j len; j n; j) { dp[j] max(dp[j], dp[j - len] price[len]); } } cout dp[n]; return 0; } 思维导图条形蛋糕 │ ▼ 本质是什么 │ ▼ 完全背包 │ ▼ 状态定义 dp[i] 长度i最大收益 │ ▼ 最后一块长度是多少 │ ▼ 枚举最后一块 │ ▼ dp[i]max(dp[i],dp[i-j]price[j]) │ ▼ 为什么正序 │ ▼ 一种长度可以无限使用 │ ▼ 完全背包 举一反三这道题其实就是经典的钢条切割Rod Cutting问题它与完全背包是同一种动态规划模型。因此当你以后遇到下面这些题目时都可以想到这套思路 蛋糕切割 钢条切割 木棍切割 绳子切割 零钱兑换求最大价值类 完全背包它们的共同特点都是一种物品或一种长度可以使用无限次因此内层循环采用正序枚举。这也是本题希望考查的核心能力。