宠物小精灵之收服

题目描述

小智有 $N$ 个精灵球，皮卡丘有 $M$ 点体力，狩猎场里有 $K$ 只野生小精灵：收服第 $i$ 只要花 $v_i$ 个精灵球，且皮卡丘损失 $u_i$ 点体力；每只至多收服一次，若收服会使体力降到 $0$ 及以下则狩猎结束，这只也收服不到。

输入：第一行 $N\ M\ K$ ，接下来 $K$ 行每行 $v_i\ u_i$ 。输出：一行两个整数 $C\ R$ ——最多收服 $C$ 只，并在收服数量最多时输出皮卡丘剩余体力的最大值 $R$ 。数据范围： $N \leqslant 1000$ ， $M \leqslant 500$ ， $K \leqslant 100$ 。

样例 1 输入 10 100 5，五只依次为 (7,10) (2,40) (2,50) (1,20) (4,20)，输出 3 30（收服第 1、2、4 只，受伤 70，剩余 30）；样例 2 输入 10 100 5，五只依次为 (8,110) (12,10) (20,10) (5,200) (1,110)，输出 0 100（每只单独都不合法）。

思路

二维费用 0/1 背包：每只小精灵价值为 1，费用是（球数 $v$ ，伤害 $u$ ），设 dp[j][p] 为球数不超过 j、伤害不超过 p 时的最大收服数，转移 dp[j][p] = max(dp[j][p], dp[j-v][p-u] + 1)，两个维度都倒序枚举保证每只至多收服一次。伤害预算取 $M-1$ 而不是 $M$ ，因为伤害总和必须小于 $M$ ，体力才不会降到 0。第一答案 $C = dp[N][M-1]$ ；dp[N][p] 随 p 单调不减，首个达到 $C$ 的 p 就是最小伤害， $R = M - p$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:40
# update_at: 2026-09-30 03:43

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    balls = next(data)  # 题面第一维：小智拥有的精灵球数量，是花费上限
    power = next(data)  # 题面第二维：皮卡丘的初始体力
    kinds = next(data)  # 野生小精灵的种类数

    # dp[ball_limit][hp_limit]：精灵球不超过 ball_limit、体力消耗不超过 hp_limit 时的最大收服数。
    # 体力维只开到 power-1：题面规定体力降到 0 或以下就必须结束狩猎，那只小精灵也收服不了。
    hp_cap = power - 1
    dp = [[0] * (hp_cap + 1) for _ in range(balls + 1)]

    for _ in range(kinds):
        cost_ball = next(data)  # 收服这只小精灵要用的精灵球
        cost_hp = next(data)    # 收服过程中皮卡丘要承受的伤害
        if cost_ball > balls or cost_hp > hp_cap:
            continue  # 这一只无论如何都收服不了，直接跳过，省掉整轮双维扫描

        # 两个维度都要倒序：它们共用同一只小精灵，正序会让这只被重复收服。
        for ball_limit in range(balls, cost_ball - 1, -1):
            row = dp[ball_limit]
            src = dp[ball_limit - cost_ball]
            for hp_limit in range(hp_cap, cost_hp - 1, -1):
                better = src[hp_limit - cost_hp] + 1  # 收服这一只：先在低一档的花费里再加 1
                if better > row[hp_limit]:
                    row[hp_limit] = better

    # 主目标收服数量最多，次目标皮卡丘受伤最少；球数只是花费上限，不参与比较。
    best = dp[balls][hp_cap]
    min_hp = dp[balls].index(best)  # 这一行随体力上限单调不减，首个达到 best 的下标就是最少消耗
    print(best, power - min_hp)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:18
 * update_at: 2026-10-05 08:18
 */

/*
 * 二维费用 0/1 背包：
 * 每只小精灵价值为 1，花费是（精灵球数 v，体力伤害 u）。
 * 体力上限是 M-1：题面要求体力降到 0 或以下时狩猎结束，
 * 那只小精灵也收服不了，所以伤害总和必须 < M。
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 1005; // 精灵球数量上限
const int MAXM = 505;  // 皮卡丘体力上限

int n, m, k;           // 精灵球数、初始体力、小精灵只数
int dp[MAXN][MAXM];    // dp[j][p]：球数 <= j、伤害 <= p 时最多收服几只

int main() {
    scanf("%d %d %d", &n, &m, &k);
    int hp_cap = m - 1; // 伤害总和必须 < m，伤害维只开到 m-1

    for (int i = 1; i <= k; ++i) {
        int v, u; // 收服这只需要的精灵球数、对皮卡丘的伤害
        scanf("%d %d", &v, &u);
        if (v > n || u > hp_cap) continue; // 这一只无论如何都收服不了

        // 两个维度都要倒序：正序会让同一只小精灵被重复收服（变成完全背包）
        for (int j = n; j >= v; --j)
            for (int p = hp_cap; p >= u; --p)
                if (dp[j - v][p - u] + 1 > dp[j][p])
                    dp[j][p] = dp[j - v][p - u] + 1;
    }

    // 第一答案：最多收服数量
    int best = dp[n][hp_cap];

    // 次答案：dp[n][p] 随 p 单调不减，首个达到 best 的 p 就是最小伤害
    int min_hp = 0;
    for (int p = 0; p <= hp_cap; ++p)
        if (dp[n][p] == best) {
            min_hp = p;
            break;
        }

    printf("%d %d\n", best, m - min_hp);
    return 0;
}