题解 | 古代仪式的准备

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int E_req = scanner.nextInt();  // 仪式所需的最小魔力能源
        int M_budget = scanner.nextInt();  // 法力值上限
        int n = scanner.nextInt();  // 魔法媒介的数量

        int[] E = new int[n]; // 存储每种媒介提供的魔力能源
        int[] M = new int[n]; // 存储每种媒介消耗的法力值

        for (int i = 0; i < n; i++) {
            E[i] = scanner.nextInt();
            M[i] = scanner.nextInt();
        }

        // 初始化动态规划数组，dp[i]表示消耗i点法力时能获得的最大魔力能源
        int[] dp = new int[M_budget + 1];
        for (int i = 0; i <= M_budget; i++) {
            dp[i] = -1; // 初始化为-1，表示无法达到
        }
        dp[0] = 0; // 消耗0点法力时获得0点魔力能源

        // 动态规划填充数组
        for (int i = 0; i < n; i++) {
            for (int j = M_budget; j >= M[i]; j--) {
                if (dp[j - M[i]] != -1) {
                    if (dp[j] < dp[j - M[i]] + E[i]) {
                        dp[j] = dp[j - M[i]] + E[i];
                    }
                }
            }
        }

        int minMana = Integer.MAX_VALUE; // 最小法力消耗
        int maxEnergy = 0; // 对应的最大魔力能源

        // 查找满足E_total >= E_req的最小法力消耗
        for (int i = 0; i <= M_budget; i++) {
            if (dp[i] >= E_req) {
                if (i < minMana) {
                    minMana = i;
                    maxEnergy = dp[i];
                }
            }
        }

        // 输出结果
        if (minMana != Integer.MAX_VALUE) {
            System.out.println(minMana  + " " + maxEnergy);
        } else {
            System.out.println("0 0");
        }
    }
}