题解 | #奶油蛋糕的进阶配方#

题目链接

题目描述

小红计划制作一系列进阶蛋糕来提升“甜度等级”。共有 $N$ 种蛋糕配方，每种限产一个。对于第 $i$ 种蛋糕，制作门槛为 $M_i$ （当前等级 $\ge M_i$ 才能制作），消耗体力 $E_i$ ，提升等级 $S_i$ 。初始等级为 $L_0$ ，总体力为 $P$ ，最多制作 $K$ 个蛋糕。求在体力允许且数量不超过 $K$ 的前提下，最终能达到的最大等级，以及达到该等级所需的最少蛋糕数量。

解题思路

本题是一个带有“开启门槛”约束的二维 0/1 背包问题。

排序预处理：由于制作蛋糕会提升甜度等级，而某些蛋糕的制作需要达到一定的等级门槛 $M_i$ ，因此我们应该优先考虑门槛较低的蛋糕。我们将所有蛋糕按照门槛 $M_i$ 从小到大进行排序。这样可以确保在处理第 $i$ 种蛋糕时，如果它能被制作，那么所有之前考虑过且决定制作的蛋糕已经尽可能地提升了当前的甜度等级。
状态定义：使用 $dp[j][e]$ 表示制作了 $j$ 个蛋糕、消耗了 $e$ 点体力时能达到的最大甜度等级。
- $0 \le j \le K$
- $0 \le e \le P$
状态转移：初始化 $dp[0][0] = L_0$ ，其余状态初始化为 $-1$ （表示不可达）。遍历排序后的每种蛋糕 $(M_i, S_i, E_i)$ ：
- 逆序遍历制作数量 $j$ 从 $\min(i+1, K)$ 到 $1$ 。
- 逆序遍历消耗体力 $e$ 从 $P$ 到 $E_i$ 。
- 如果满足门槛限制 $dp[j - 1][e - E_i] \ge M_i$ 且前一状态可达（ $dp[j - 1][e - E_i] > -1$ ）： $dp[j][e] = \max(dp[j][e], dp[j - 1][e - E_i] + S_i)$
结果统计：遍历所有的 $dp[j][e]$ ，找到全局最大值 $max\_level$ 。在甜度相同的情况下，记录最小的制作数量 $j$ 。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 蛋糕结构体
struct Cake {
    int m, s, e;
};

int main() {
    int n, l0, p_limit, k_limit;
    cin >> n >> l0 >> p_limit >> k_limit;

    vector<Cake> cakes(n);
    vector<int> m(n), s(n), e(n);
    for (int i = 0; i < n; ++i) cin >> m[i];
    for (int i = 0; i < n; ++i) cin >> s[i];
    for (int i = 0; i < n; ++i) cin >> e[i];
    for (int i = 0; i < n; ++i) cakes[i] = {m[i], s[i], e[i]};

    // 按照门槛 M 升序排序
    sort(cakes.begin(), cakes.end(), [](const Cake& a, const Cake& b) {
        return a.m < b.m;
    });

    // dp[j][e] 表示制作 j 个蛋糕消耗 e 体力后的最大甜度
    vector<vector<long long>> dp(k_limit + 1, vector<long long>(p_limit + 1, -1));
    dp[0][0] = (long long)l0;

    for (int i = 0; i < n; ++i) {
        for (int j = k_limit; j >= 1; --j) {
            for (int e_cur = p_limit; e_cur >= cakes[i].e; --e_cur) {
                if (dp[j - 1][e_cur - cakes[i].e] >= cakes[i].m) {
                    dp[j][e_cur] = max(dp[j][e_cur], dp[j - 1][e_cur - cakes[i].e] + cakes[i].s);
                }
            }
        }
    }

    long long max_sweetness = l0;
    int min_count = 0;

    for (int j = 0; j <= k_limit; ++j) {
        for (int e_cur = 0; e_cur <= p_limit; ++e_cur) {
            if (dp[j][e_cur] > max_sweetness) {
                max_sweetness = dp[j][e_cur];
                min_count = j;
            } else if (dp[j][e_cur] == max_sweetness && dp[j][e_cur] != -1) {
                if (min_count > j) min_count = j;
            }
        }
    }

    cout << max_sweetness << " " << min_count << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class Cake {
        int m, s, e;
        Cake(int m, int s, int e) {
            this.m = m;
            this.s = s;
            this.e = e;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l0 = sc.nextInt();
        int pLimit = sc.nextInt();
        int kLimit = sc.nextInt();

        int[] mArr = new int[n];
        int[] sArr = new int[n];
        int[] eArr = new int[n];
        for (int i = 0; i < n; i++) mArr[i] = sc.nextInt();
        for (int i = 0; i < n; i++) sArr[i] = sc.nextInt();
        for (int i = 0; i < n; i++) eArr[i] = sc.nextInt();

        Cake[] cakes = new Cake[n];
        for (int i = 0; i < n; i++) {
            cakes[i] = new Cake(mArr[i], sArr[i], eArr[i]);
        }

        // 按门槛排序
        Arrays.sort(cakes, (a, b) -> Integer.compare(a.m, b.m));

        // dp[j][e] 存储最大甜度
        long[][] dp = new long[kLimit + 1][pLimit + 1];
        for (int i = 0; i <= kLimit; i++) {
            Arrays.fill(dp[i], -1);
        }
        dp[0][0] = l0;

        for (int i = 0; i < n; i++) {
            for (int j = kLimit; j >= 1; j--) {
                for (int eCur = pLimit; eCur >= cakes[i].e; eCur--) {
                    if (dp[j - 1][eCur - cakes[i].e] >= cakes[i].m) {
                        dp[j][eCur] = Math.max(dp[j][eCur], dp[j - 1][eCur - cakes[i].e] + cakes[i].s);
                    }
                }
            }
        }

        long maxSweetness = l0;
        int minCount = 0;
        for (int j = 0; j <= kLimit; j++) {
            for (int eCur = 0; eCur <= pLimit; eCur++) {
                if (dp[j][eCur] > maxSweetness) {
                    maxSweetness = dp[j][eCur];
                    minCount = j;
                } else if (dp[j][eCur] == maxSweetness && dp[j][eCur] != -1) {
                    if (minCount > j) minCount = j;
                }
            }
        }
        System.out.println(maxSweetness + " " + minCount);
    }
}

def solve():
    # 读取输入
    line1 = input().split()
    if not line1: return
    n, l0, p_limit, k_limit = map(int, line1)
    
    m_list = list(map(int, input().split()))
    s_list = list(map(int, input().split()))
    e_list = list(map(int, input().split()))
    
    cakes = []
    for i in range(n):
        cakes.append((m_list[i], s_list[i], e_list[i]))
        
    # 按照门槛 m 升序排序
    cakes.sort()
    
    # dp[j][e] 表示制作 j 个蛋糕、消耗 e 体力后的最大甜度
    dp = [[-1] * (p_limit + 1) for _ in range(k_limit + 1)]
    dp[0][0] = l0
    
    for m, s, e in cakes:
        for j in range(k_limit, 0, -1):
            for e_cur in range(p_limit, e - 1, -1):
                if dp[j - 1][e_cur - e] >= m:
                    new_val = dp[j - 1][e_cur - e] + s
                    if new_val > dp[j][e_cur]:
                        dp[j][e_cur] = new_val
                        
    max_sweetness = l0
    min_count = 0
    
    for j in range(k_limit + 1):
        for e_cur in range(p_limit + 1):
            if dp[j][e_cur] > max_sweetness:
                max_sweetness = dp[j][e_cur]
                min_count = j
            elif dp[j][e_cur] == max_sweetness and dp[j][e_cur] != -1:
                if j < min_count:
                    min_count = j
                    
    print(f"{max_sweetness} {min_count}")

solve()

算法及复杂度

算法：动态规划（带有门槛约束的二维 0/1 背包问题）。
时间复杂度： $\mathcal{O}(N \log N + N \cdot K \cdot P)$ 。其中 $N$ 是蛋糕种类， $K$ 是最大制作数量， $P$ 是体力限制。
空间复杂度： $\mathcal{O}(K \cdot P)$ 。用于存储动态规划的状态。