题解 | 古代仪式的准备

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const INF = -1 << 30 // 表示不可达

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	// 读取 E_req, M_budget, n
	nextInt := func() int {
		scanner.Scan()
		x, _ := strconv.Atoi(scanner.Text())
		return x
	}

	E_req := nextInt()
	M_budget := nextInt()
	n := nextInt()

	// 存储媒介
	media := make([][2]int, n) // [E_i, M_i]
	for i := 0; i < n; i++ {
		E_i, M_i := nextInt(), nextInt()
		media[i] = [2]int{E_i, M_i}
	}

	// DP: dp[m] = 消耗恰好 m 法力时能获得的最大能源
	dp := make([]int, M_budget+1)
	for i := range dp {
		dp[i] = INF
	}
	dp[0] = 0 // 不选任何媒介，能源为0

	// 0-1背包
	for _, med := range media {
		E_i, M_i := med[0], med[1]
		// 逆序遍历，避免重复选择
		for m := M_budget; m >= M_i; m -= 10 {
			if dp[m-M_i] != INF {
				if dp[m] < dp[m-M_i]+E_i {
					dp[m] = dp[m-M_i] + E_i
				}
			}
		}
		/*
		   特性	        逆序（从大到小）	      正序（从小到大）
		   物品使用次数    最多一次（0-1背包）	     可多次使用（完全背包）
		   依赖状态	  未被本轮更新的旧状态	   可能已被本轮更新的新状态
		*/
	}

	// 寻找最优解
	minMana := M_budget + 1 // 初始化为不可达
	maxEnergy := 0

	for m := 0; m <= M_budget; m += 10 {
		if dp[m] >= E_req { // 满足魔力能源
			if m < minMana { // 更少的法力消耗
				minMana = m
				maxEnergy = dp[m]
			} else if m == minMana && dp[m] > maxEnergy { // 相等法力消耗下，更多魔力能源
				maxEnergy = dp[m]
			}
		}
	}

	// 输出结果
	if minMana > M_budget { // 法力不足
		fmt.Println("0 0")
	} else {
		fmt.Println(minMana, maxEnergy)
	}
}