04102: 宠物小精灵之收服

dp, http://cs101.openjudge.cn/practice/04102/

宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。

一天，小智和皮卡丘来到了小精灵狩猎场，里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而，野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害（从而减少皮卡丘的体力）。当皮卡丘的体力小于等于0时，小智就必须结束狩猎（因为他需要给皮卡丘疗伤），而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时，狩猎也宣告结束。

我们假设小智遇到野生小精灵时有两个选择：收服它，或者离开它。如果小智选择了收服，那么一定会扔出能够收服该小精灵的精灵球，而皮卡丘也一定会受到相应的伤害；如果选择离开它，那么小智不会损失精灵球，皮卡丘也不会损失体力。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小（剩余体力越大），因为他们还要继续冒险。

现在已知小智的精灵球数量和皮卡丘的初始体力，已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问，小智该如何选择收服哪些小精灵以达到他的目标呢？

输入

输入数据的第一行包含三个整数：N(0 < N < 1000)，M(0 < M < 500)，K(0 < K < 100)，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。之后的K行，每一行代表一个野生小精灵，包括两个整数：收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害。

输出

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

样例输入

样例输出

样例输出1：
3 30

样例输出2：
0 100

提示

对于样例输入1：小智选择：(7,10) (2,40) (1,20) 这样小智一共收服了3个小精灵，皮卡丘受到了70点伤害，剩余100-70=30点体力。所以输出3 30 对于样例输入2：小智一个小精灵都没法收服，皮卡丘也不会收到任何伤害，所以输出0 100

二维费用01背包

dp 是一个二维列表，dp[i][j] 表示在收服了 i 个小精灵且皮卡丘剩余 j 体力的情况下，小智还剩下的精灵球数量。
dp[0][M] = N 表示初始状态，没有收服任何小精灵，皮卡丘的初始体力为 M，小智有 N 个精灵球。

python

N, M, K = map(int, input().split())
dp = [[-1] * (M + 1) for i in range(K + 1)]
dp[0][M] = N
for i in range(K):
    cost, dmg = map(int, input().split())
    for p in range(M):
        for q in range(i + 1, 0, -1):
            if p + dmg <= M and dp[q - 1][p + dmg] != -1:
                dp[q][p] = max(dp[q][p], dp[q - 1][p + dmg] - cost)


def find():
    for i in range(K, -1, -1):
        for j in range(M, -1, -1):
            if dp[i][j] != -1:
                return i, j


captured, remaining_life = find()
print(captured, remaining_life)

python

# 官祺云 24 物理学院
"""
四个参数：个数K，限制N，限制M，值num。如果以MN为限制去找最大num，那么K*N*M会TLE。
这时注意到num也有限制num<=K，故可以选择把num改成其中一个限制，去寻找最小的N，
时间就会变成K*M*K，就不会TLE
"""
N, M, K = map(int, input().split())
n = [0] * K
m = [0] * K

dp = [[float('inf')] * (M + 1) for i in range(K + 1)]
dp[0][0] = 0
for i in range(K):
    cost, dmg = map(int, input().split())
    for j in range(M, dmg - 1, -1):
        for k in range(i + 1, 0, -1):
            if dp[k - 1][j - dmg] + cost <= N:
                dp[k][j] = min(dp[k][j], dp[k - 1][j - dmg] + cost)


def find():
    for i in range(K, -1, -1):
        for j in range(M + 1):
            if dp[i][j] != float('inf'):
                return i, M - j


captured, remaining_life = find()
print(captured, remaining_life)

python

# 1984ms AC
N, M, K = map(int, input().split())

# 初始化DP数组
dp = [[float('inf')] * (K + 1) for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0  # 当不收服任何小精灵时，皮卡丘的体力消耗为0

# 读取每个小精灵的信息
for i in range(1, K + 1):
    u, v = map(int, input().split())
    for j in range(N, u - 1, -1):  # 从后向前遍历以避免重复计算
        for r in range(i, 0, -1):
            if dp[j - u][r - 1] != float('inf'):
                dp[j][r] = min(dp[j][r], dp[j - u][r - 1] + v)

# 找到最大收服数量
max_captured = 0
min_energy_used = M
for i in range(K, -1, -1):
    if dp[N][i] < M:
        max_captured = i
        min_energy_used = M - dp[N][i]
        break

# 输出结果
print(max_captured, min_energy_used)

66ms AC

python

# 刘思昊，24工学院
n, m, k = map(int, input().split())
wild_pokemon = []
for _ in range(k):
    balls, damage = map(int, input().split())
    wild_pokemon.append((balls, damage))

# 按伤害升序排序
wild_pokemon.sort(key=lambda x: x[1])

# 初始化 DP 数组
dp = [[0, 0] for _ in range(n + 1)]  # dp[i] = [最大收服数, 总伤害]

for balls, damage in wild_pokemon:
    for i in range(n, balls - 1, -1):
        prev_num, prev_damage = dp[i - balls]
        if prev_damage + damage >= m:  # 超过体力限制，跳过
            continue
        # 更新 DP：选择更优方案
        if prev_num + 1 > dp[i][0]:
            dp[i] = [prev_num + 1, prev_damage + damage]
        elif prev_num + 1 == dp[i][0]:
            dp[i][1] = min(dp[i][1], prev_damage + damage)


max_captured, total_damage = dp[-1]
print(max_captured, m - total_damage)

思路是 动态规划 + 贪心，并通过对小精灵列表按伤害值 (hp) 升序排序来优化结果。以下是对其正确性的分析和改进建议：
算法说明
排序优化:
按照伤害值升序排列小精灵后，优先考虑那些对皮卡丘伤害较小的小精灵。
这种排序确保了在尽量收服更多小精灵的情况下，皮卡丘的剩余体力尽可能多。
动态规划:
dp[i] = [num, hp]：表示使用了 i 个精灵球时，最多能收服的精灵数 num 和相应情况下皮卡丘所受的总伤害 hp。
状态转移公式：
如果当前精灵可以被收服（即精灵球数足够，且皮卡丘体力不至于小于等于 0）：
python
dp[i] = max(dp[i], [dp[i-ball][0] + 1, dp[i-ball][1] + hp])
在数量相等时比较伤害值，取伤害值更小的方案。
复杂度分析:
预排序的时间复杂度为 $O (K \log K)$ 。
动态规划部分的复杂度为 $O (K \times N)$ ，因为每个小精灵需要遍历精灵球的使用情况。
正确性分析
该算法的思想与经典的 0-1 背包问题 类似，目的是在有限资源（精灵球和皮卡丘体力）的约束下，优化两个目标：
收服小精灵的数量（主目标）；
剩余体力的最大化（次目标）。
排序的贪心性
排序确保了优先考虑对皮卡丘伤害较小的小精灵，减少了高伤害精灵对后续选择的影响。因为动态规划的顺序遍历会保留最优解，所以排序不会影响结果的正确性。

04102: 宠物小精灵之收服 ​

04102: 宠物小精灵之收服