题解 | #遗迹探险家小红#

题目链接

题目描述

小红在遗迹中收集宝藏，共有 $N$ 件宝藏。第 $i$ 件宝藏收集耗时 $t_i$ 分钟，价值为 $v_i$ 。小红的总探险时间不得超过 $T$ 分钟。此外，若 $t_i > 30$ ，该宝藏被视为“重型宝藏”，收集的重型宝藏总数不得超过 $K$ 个。每件宝藏最多收集一次。求能获得的最大价值总和。

解题思路

本题是一个典型的带额外约束条件的 0/1 背包问题。

状态定义：我们可以使用一个二维动态规划数组 $dp[j][k]$ 来表示在总耗时为 $j$ 分钟，且收集了 $k$ 个重型宝藏时所能获得的最大价值。
- $j$ 的范围是 $0 \le j \le T$ 。
- $k$ 的范围是 $0 \le k \le K$ 。
状态转移：遍历每一件宝藏 $(t_i, v_i)$ ：
- 如果 $t_i > T$ ，该宝藏无论如何都无法收集，直接跳过。
- 如果 $t_i \le 30$ （普通宝藏）：对于每一个 $j$ 从 $T$ 到 $t_i$ ，以及每一个 $k$ 从 $0$ 到 $K$ ： $dp[j][k] = \max(dp[j][k], dp[j - t_i][k] + v_i)$
- 如果 $t_i > 30$ （重型宝藏）：对于每一个 $j$ 从 $T$ 到 $t_i$ ，以及每一个 $k$ 从 $K$ 到 $1$ ： $dp[j][k] = \max(dp[j][k], dp[j - t_i][k - 1] + v_i)$
结果计算：最终结果为 $\max(dp[j][k])$ ，其中 $0 \le j \le T$ 且 $0 \le k \le K$ 。
注意事项：
- 由于宝藏价值 $v_i$ 可能较大，需要使用 64 位整数（C++ 中的 long long，Java 中的 long）。
- 为了节省空间，我们使用了滚动数组的思想，逆序遍历时间 $j$ 。

代码

c++
java
python

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

using namespace std;

/**
 * 这是一个带有二维约束的 0/1 背包问题
 * 第一维约束：总时间 T
 * 第二维约束：重型宝藏数量 K
 */

int main() {
    int n, t_limit, k_limit;
    cin >> n >> t_limit >> k_limit;

    // dp[j][k] 表示总耗时 j 且重型宝藏数为 k 时的最大价值
    // 使用 long long 避免价值总和溢出
    vector<vector<long long>> dp(t_limit + 1, vector<long long>(k_limit + 1, 0));

    for (int i = 0; i < n; ++i) {
        int t, v;
        cin >> t >> v;
        if (t > t_limit) continue;

        if (t <= 30) {
            // 普通宝藏：不增加重型宝藏计数
            for (int j = t_limit; j >= t; --j) {
                for (int k = 0; k <= k_limit; ++k) {
                    dp[j][k] = max(dp[j][k], dp[j - t][k] + v);
                }
            }
        } else {
            // 重型宝藏：增加重型宝藏计数
            for (int j = t_limit; j >= t; --j) {
                for (int k = k_limit; k >= 1; --k) {
                    dp[j][k] = max(dp[j][k], dp[j - t][k - 1] + v);
                }
            }
        }
    }

    long long max_val = 0;
    for (int j = 0; j <= t_limit; ++j) {
        for (int k = 0; k <= k_limit; ++k) {
            max_val = max(max_val, dp[j][k]);
        }
    }

    cout << max_val << endl;

    return 0;
}

import java.util.Scanner;

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

        // dp[j][k] 表示时间为 j，重型宝藏数量为 k 时的最大价值
        long[][] dp = new long[tLimit + 1][kLimit + 1];

        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            int v = sc.nextInt();
            if (t > tLimit) continue;

            if (t <= 30) {
                // 普通宝藏：k 不变
                for (int j = tLimit; j >= t; j--) {
                    for (int k = 0; k <= kLimit; k++) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - t][k] + v);
                    }
                }
            } else {
                // 重型宝藏：k 增加
                for (int j = tLimit; j >= t; j--) {
                    for (int k = kLimit; k >= 1; k--) {
                        dp[j][k] = Math.max(dp[j][k], dp[j - t][k - 1] + v);
                    }
                }
            }
        }

        long ans = 0;
        for (int j = 0; j <= tLimit; j++) {
            for (int k = 0; k <= kLimit; k++) {
                ans = Math.max(ans, dp[j][k]);
            }
        }
        System.out.println(ans);
    }
}

def solve():
    # 读取宝藏总数 n、总时间限制 t_limit 和重型宝藏限制 k_limit
    line1 = input().split()
    n, t_limit, k_limit = map(int, line1)

    # dp[j][k] 表示消耗 j 时间且包含 k 个重型宝藏时的最大价值
    dp = [[0] * (k_limit + 1) for _ in range(t_limit + 1)]

    for _ in range(n):
        t, v = map(int, input().split())
        if t > t_limit:
            continue

        if t <= 30:
            # 普通宝藏处理：重型宝藏数 k 不增加
            for j in range(t_limit, t - 1, -1):
                for k in range(k_limit + 1):
                    new_val = dp[j - t][k] + v
                    if new_val > dp[j][k]:
                        dp[j][k] = new_val
        else:
            # 重型宝藏处理：重型宝藏数 k 增加
            for j in range(t_limit, t - 1, -1):
                for k in range(k_limit, 0, -1):
                    new_val = dp[j - t][k - 1] + v
                    if new_val > dp[j][k]:
                        dp[j][k] = new_val

    # 找到所有状态中的最大值
    ans = 0
    for row in dp:
        current_max = max(row)
        if current_max > ans:
            ans = current_max
    
    print(ans)

solve()

算法及复杂度

算法：二维约束 0/1 背包（动态规划）。
时间复杂度： $\mathcal{O}(N \cdot T \cdot K)$ 。其中 $N$ 是宝藏数量， $T$ 是最大允许总时间， $K$ 是重型宝藏最大数量。
空间复杂度： $\mathcal{O}(T \cdot K)$ 。使用了二维滚动数组存储状态。