题解 | #古代仪式的准备#

题目链接

古代仪式的准备

题目描述

为了启动一个古代仪式，需要在法力值上限 $M_{max}$ 内，选择一组魔法媒介，使得它们提供的总魔力能源 $E_{total}$ 不低于仪式的最低需求 $E_{min}$ 。

任务是，在所有满足 $E_{total} \ge E_{min}$ 的组合中，找到一个法力总消耗 $M_{total}$ 最小的方案。如果存在多个法力消耗同为最小的方案，则选择其中 $E_{total}$ 最大的一个。

输入:

一行三个整数 $E_{min}, M_{max}, N$ 。
接下来 $N$ 行，每行包含两个整数 $E_i, M_i$ ，分别代表第 $i$ 种媒介提供的能源和消耗的法力。

输出:

输出满足条件的最小法力总消耗，以及在该消耗下能获得的最大魔力能源。
如果无法满足最低能源需求，则输出 0 0。

解题思路

这是一个典型的0/1背包问题的变种。我们可以将法力值看作背包的“重量”，魔力能源看作物品的“价值”。

传统的背包问题是在给定“重量”上限的情况下，求能获得的最大“价值”。而本题的目标是，在“价值”达到某个阈值（ $E_{min}$ ）的前提下，求所需的最少“重量”（ $M_{total}$ ），并在此最少“重量”下最大化“价值”。

我们可以使用动态规划来解决此问题。定义一个DP数组 $dp$ ：

$dp[j]$ : 表示当法力值总消耗恰好为 $j$ 时，所能获得的最大魔力能源。

状态转移方程: 当我们考虑第 $i$ 个物品（能源为 $E_i$ ，法力消耗为 $M_i$ ）时，对于一个给定的法力消耗 $j$ ，我们有两种选择：

不选择第 $i$ 个物品：最大能源仍然是之前的 $dp[j]$ 。
选择第 $i$ 个物品：这要求我们之前的法力消耗为 $j - M_i$ ，在此基础上获得 $E_i$ 的能源。此时的最大能源为 $dp[j - M_i] + E_i$ 。

因此，状态转移方程为： $dp[j] = \max(dp[j], dp[j - M_i] + E_i)$

实现步骤:

创建一个大小为 $M_{max} + 1$ 的DP数组 $dp$ 。将 $dp[0]$ 初始化为0，其余位置初始化为一个特殊值（如-1），表示该状态不可达。
遍历每一种魔法媒介（物品）。对于每种媒介，我们逆序遍历法力值 $j$ （从 $M_{max}$ 到 $M_i$ ），并根据上述状态转移方程更新 $dp[j]$ 。逆序遍历是为了保证每个物品只被选择一次（0/1背包的特性）。
DP表填充完毕后， $dp[j]$ 就存储了消耗法力为 $j$ 时能获得的最大能源。我们从小到大遍历所有可能的法力消耗 $m$ (从 1 到 $M_{max}$ )。
找到第一个满足 $dp[m] \ge E_{min}$ 的 $m$ 。这个 $m$ 就是我们尋找的最小法力消耗。对应的最大能源就是 $dp[m]$ 。直接输出 $m$ 和 $dp[m]$ 并结束程序。
如果遍历完所有可能的法力消耗后，都未能满足条件，则说明仪式无法启动，输出 0 0。

代码

cpp
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long e_min;
    int m_max, n;
    cin >> e_min >> m_max >> n;

    vector<pair<int, int>> items(n);
    for (int i = 0; i < n; ++i) {
        cin >> items[i].first >> items[i].second;
    }

    // dp[j] 表示消耗法力为 j 时能获得的最大能源
    vector<long long> dp(m_max + 1, -1);
    dp[0] = 0;

    for (int i = 0; i < n; ++i) {
        int energy = items[i].first;
        int mana = items[i].second;
        for (int j = m_max; j >= mana; --j) {
            // 如果 j - mana 这个状态是可达的
            if (dp[j - mana] != -1) {
                dp[j] = max(dp[j], dp[j - mana] + energy);
            }
        }
    }

    int best_mana = 0;
    long long max_energy = 0;

    for (int m = 1; m <= m_max; ++m) {
        if (dp[m] >= e_min) {
            best_mana = m;
            max_energy = dp[m];
            cout << best_mana << " " << max_energy << endl;
            return 0;
        }
    }

    cout << "0 0" << endl;
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

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

        int[][] items = new int[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = sc.nextInt(); // energy
            items[i][1] = sc.nextInt(); // mana
        }

        // dp[j] 表示消耗法力为 j 时能获得的最大能源
        long[] dp = new long[mMax + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            int energy = items[i][0];
            int mana = items[i][1];
            for (int j = mMax; j >= mana; j--) {
                // 如果 j - mana 这个状态是可达的
                if (dp[j - mana] != -1) {
                    dp[j] = Math.max(dp[j], dp[j - mana] + energy);
                }
            }
        }

        for (int m = 1; m <= mMax; m++) {
            if (dp[m] >= eMin) {
                System.out.println(m + " " + dp[m]);
                return;
            }
        }

        System.out.println("0 0");
    }
}

e_min, m_max, n = map(int, input().split())
items = []
for _ in range(n):
    items.append(list(map(int, input().split())))

# dp[j] 表示消耗法力为 j 时能获得的最大能源
dp = [-1] * (m_max + 1)
dp[0] = 0

for energy, mana in items:
    for j in range(m_max, mana - 1, -1):
        # 如果 j - mana 这个状态是可达的
        if dp[j - mana] != -1:
            dp[j] = max(dp[j], dp[j - mana] + energy)

found = False
for m in range(1, m_max + 1):
    if dp[m] >= e_min:
        print(m, dp[m])
        found = True
        break

if not found:
    print("0 0")

算法及复杂度

算法：动态规划 (0/1背包问题)
时间复杂度： $\mathcal{O}(N \cdot M_{max})$ ，其中 $N$ 是魔法媒介的数量， $M_{max}$ 是法力值上限。我们需要两层循环来填充DP表。
空间复杂度： $\mathcal{O}(M_{max})$ ，用于存储DP数组。