G6023 [GESP202606 六级] 条形蛋糕 题解

知识点：完全背包、动态规划、整数划分。

解题思路

令dp[i]为长度i蛋糕的最大收益，枚举最后一段长度j，取dp[i-j]+a[j]的最大值。

为什么正确

任意切法去掉最后一段后仍是长度i-j的切法，最优子结构与全部j的枚举保证最优。

易错点

可多次切出相同长度；要求总长度恰为n，状态不能混入没有用完的长度。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>a(n+1),dp(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)dp[i]=max(dp[i],dp[i-j]+a[j]);
    cout<<dp[n];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。