OpenJudge NOI 2.6 4978题解：宠物小精灵之收服（含测试数据与避坑指南）

从二维费用背包到实战优化：深入解析“宠物小精灵之收服”的竞赛解法

最近在辅导一些准备 信息 学奥赛的学生时，我发现“宠物小精灵之收服”这道题出现的频率相当高。它不仅是OpenJudge NOI 2.6的经典题目，也经常出现在各类模拟赛中。很多同学初次接触时，会觉得它就是个简单的背包问题，但真正动手编码后，却往往在边界条件、内存限制和最优解的第二问上栽跟头。今天，我就结合自己带学生刷题的经验，把这道题里里外外拆解一遍，不仅告诉你标准解法，更分享一些实战中能帮你省下宝贵时间的技巧和避坑指南。

这道题的核心，是资源有限下的最优决策。你手上有一定数量的精灵球，皮卡丘有一定的体力值，每个野生小精灵捕获时需要消耗特定数量的精灵球，同时会对皮卡丘造成固定的伤害。目标很明确：在皮卡丘体力不耗尽的前提下，尽可能多地收服小精灵，并且在收服数量最多的前提下，让皮卡丘剩余体力尽可能多。这听起来就像生活中常见的预算规划问题，只不过这里的“预算”变成了两种：精灵球和体力。

1. 问题本质与 建模 ：当背包有了两个维度

我们首先得抛开“宠物小精灵”这个有趣的外壳，直击问题的计算本质。你拥有的精灵球总数 n 和皮卡丘的体力上限 m，是两种独立的限制资源。每个小精灵 i 对应一个资源消耗对 (b[i], d[i])，其中 b[i] 是精灵球消耗，d[i] 是体力伤害。我们的目标是选择一个子集的小精灵进行收服，使得在总精灵球消耗 ≤ n 且总体力消耗 严格小于 m（注意这个关键点）的条件下，收服的小精灵数量最多。

这立刻让我们联想到经典的背包问题。但普通的0/1背包只有一种“重量”限制，而这里我们有“精灵球”和“体力”两种“重量”。因此，这是一个标准的二维费用背包问题。动态规划的状态需要同时记录两种资源的已使用量。

提示：在竞赛中，快速识别问题模型是第一步。看到“两种限制资源”、“每个物品消耗两种资源”、“求最大数量或价值”，就要立刻想到二维费用背包。

我们定义 dp[j][k] 表示：在最多使用 j 个精灵球和 最多 消耗 k 点体力的情况下，能够收服的小精灵最大数量。

这里有一个至关重要的细节：题目描述中提到，“如果一个小精灵让皮卡丘体力值小于等于0，那么也无法收服”。这意味着，皮卡丘的体力值必须始终大于0。换句话说，我们能使用的体力上限不是 m，而是 m-1。因为一旦使用了 m 点体力，皮卡丘体力就归零了，不符合要求。因此，在输入皮卡丘初始体力 m 后，我们首先执行 m-- 操作，将问题中的体力上限转化为“最大允许消耗的体力值”。之后的 dp 状态中的 k 都是指这个消耗值。

对于每个小精灵 i，我们有收服或不收服两种选择。状态转移方程遵循0/1背包的思想，并且因为状态有两维，我们需要逆序更新以保证每个小精灵只被使用一次：

for (int i = 1; i <= ka; ++i) {

for (int j = n; j >= b[i]; --j) {

for (int k = m; k >= d[i]; --k) {

dp[j][k] = max(dp[j][k], dp[j - b[i]][k - d[i]] + 1);

}

}

}

cpp

这个循环结束后，dp[n][m] 存储的就是我们第一个问题的答案：在最多使用 n 个球和最多消耗 m 点体力（即初始体力为 m+1）的条件下，能收服的最多小精灵数量。

很多同学会想，能不能定义一个三维数组 dp[i][j][k]，表示前 i 个小精灵、使用 j 个球、消耗 k 点体力时的最优解呢？从理解上当然可以，但我们必须评估空间复杂度。

题目典型数据范围：

相关知识

OpenJudge NOI 2.6 4978题解：宠物小精灵之收服（含测试数据与避坑指南）
4978:宠物小精灵之收服
openjudge 精灵小宠物之收服
4978:宠物小精灵之收服（0
[Acwing1022]宠物小精灵之收服
NOI 4978:宠物小精灵之收服（DP 01背包 两约束条件）
【openjudge】宠物小精灵之收服
宠物小精灵之收服（DP，二维背包问题）
（动态规划）4978:宠物小精灵之收服
魔女之泉r第二章避坑指南

网址: OpenJudge NOI 2.6 4978题解：宠物小精灵之收服（含测试数据与避坑指南） https://www.mcbbbk.com/newsview1372624.html