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}\{4\}, \{1, 3\}, \{2, 2\}, \{1, 1, 2\}, \{1, 1, 1, 1\}{4},{1,3},{2,2},{1,1,2},{1,1,1,1} 五种本质不同的分法。

其对应的总销售价格分别为 $9,9,10,7,4$，故最大总销售价格为 $10$。

第二个样例中，长度为 $10$ 的长条蛋糕，销售价格最大的分法为 {10}\{10\}{10}，最大总销售价格为 $30$。

题解

本题是一个典型的完全背包问题，不过这里物品（蛋糕块长度）的价值与长度直接对应，且每种长度可以无限次使用。
设 $dp[j]$ 表示长度为 $j$ 的蛋糕所能获得的最大总价值。初始时 $dp[0]=0$，其他 $dp[j]=0$（因为价值均为正，所以初始化为 0 不影响正确性）。
对于每个长度 $i$（$1\le i\le n$），其价格为 $p_i$，我们考虑使用长度为 $i$ 的蛋糕块，它可以被切出任意数量。由于是完全背包，我们采用正序遍历容量 $j$（从 $i$ 到 $n$），状态转移方程为：
$$dp[j]=\max (dp[j],dp[j-i]+p_i)$$
含义是：不选长度为 $i$ 的块（保持 $dp[j]$），或者选一块长度为 $i$ 的块，剩余长度 $j-i$ 继续用最优方案分割。
最终 $dp[n]$ 即为答案。

时间复杂度：两层循环，外层 $n$，内层平均 $n/2$，总 $O(n^2)$，$n\le 1000$ 完全可行。
空间复杂度：$O(n)$。

注意：本题中价格表是完整的，即 $p_i$ 已知，且每个长度均可使用多次，这正是完全背包的特征。

---

带注释的源代码

#include <bits/stdc++.h>
using namespace std;

int n;
int p;               // 临时存储当前长度 i 的价格
long long dp[1005];  // dp[j] 表示长度为 j 的蛋糕最大收益

int main() {
    cin >> n;        // 读入蛋糕总长度

    // 遍历每个长度 i (1..n)
    for (int i = 1; i <= n; i++) {
        cin >> p;    // 读入长度为 i 的蛋糕块价格

        // 完全背包正序更新，允许使用多个长度为 i 的块
        for (int j = i; j <= n; j++) {
            // 比较不选 i 与选一块 i 的价值
            dp[j] = max(dp[j], dp[j - i] + p);
        }
    }

    // 输出长度为 n 时的最大价值
    cout << dp[n];
    return 0;
}