形式化题目

有 $k$ 个气缸，第 $i$ 个气缸含氧气 $a_i$、氮气 $b_i$，重量 $c_i$。从中选出一个子集， 使子集的氧气总量 $\geqslant m$、氮气总量 $\geqslant n$（两种气体各自独立地"至少"达标， 超出部分不惩罚），求满足条件的子集的最小总重量。

样例：$m = 5$、$n = 60$，5 个气缸为 $(3,36,120)$、$(10,25,129)$、$(5,50,250)$、 $(1,45,130)$、$(4,20,119)$。选 1、2 号气缸：氧气 $3+10=5 \geqslant 5$、 氮气 $36+25=61 \geqslant 60$，总重 $120+129 = 249$，即为最小值。

正解

思路

最直接的想法是枚举 $2^k$ 个子集逐一检查，$k \leqslant 1000$ 时是天文数字； 把两个气体维度拆成两个独立的一维背包也不行——同一个气缸的氧气和氮气必须同时选或 同时不选，两个维度被"选哪个子集"牢牢耦合。可行的突破口有两条：

1. 需求是"至少"：氧气超过 $m$ 的部分毫无用处，因此不必记录真实气量， 只记录被需求收拢后的量——氧记作 $\min(x, m)$、氮记作 $\min(y, n)$。 状态数从"真实气量上界"降到 $(m+1)(n+1) \leqslant 22 \times 80 = 1760$。
2. 收拢后的转移是确定的：若收拢值 $i < m$，实际氧气恰为 $i$，放入气缸后变成 $\min(i + a, m)$；若 $i = m$，实际氧气已达标，放多少仍是 $m$。氮气同理。 所以转移只依赖收拢值本身：

于是得到二维费用 0/1 背包：状态 $dp[i][j]$ 表示只看前若干个气缸时，收拢值为 $(i, j)$ 的子集的最小总重；初始化 $dp[0][0] = 0$、其余为不可达哨兵， 逐个气缸做一轮转移，答案即 $dp[m][n]$。

对应到代码：$m$、$n$ 就是读入的 need_o、need_n（同时是状态表的两个维度）， 收拢公式落在 ni = min(i + oxygen, need_o) 与 nj = min(j + nitro, need_n)， 整个气缸的轮转移封装在 pack() 中。

两个细节决定正确性：

• 0/1 怎么保证：目标下标 $\big(\min(i+a, m), \min(j+b, n)\big)$ 总不小于当前下标， 所以把 $i$、$j$ 都从大到小枚举——目标状态先被访问、当前状态后被访问， 本轮新写入的值不会再被读到，当前气缸不可能被用第二次；而读到的 $dp[i][j]$ 在本轮尚未被改写，仍是"前若干个气缸"的结果。
• 同一收拢值为什么只留最轻的：未来转移只看收拢值，实际气量更多没有任何额外收益， 重量更小严格更好，所以逐轮取 $\min$ 不会丢掉最优子集。

下表展示样例按气缸逐轮推进的可达状态：第一列是已经处理完的气缸（一轮转移）， 第二列枚举该轮结束后所有可达的收拢状态，写法为 $(i, j) = $ 最小总重， 表中没有出现的收拢状态即为不可达：

观察两点：第 2 轮中 $(3,36)$ 放入 2 号气缸，氧气 $3+10=13$ 收拢到 $5$、 氮气 $36+25=61$ 收拢到 $60$，一步到 $(5,60)$，总重 $120+129=249$，正是题面的 "1、2 号气缸"方案；而 $(5,25)=129$ 说明单个气缸也可以氧气先超额、氮气仍欠—— 两个维度各自独立收拢，谁先达标互不影响。最后一行里 $(5,56)=239$（1、5 号气缸： 氧气 $3+4=7$ 收拢到 $5$，氮气 $36+20=56$）虽然比 $249$ 轻，氮气却还差 $4$， 不能作为答案；全部气缸处理完，$(5,60)$ 仍是 $249$，即最终答案。

代码

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
45
46
47#!/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 02:39
# update_at: 2026-09-30 02:39

import sys

INF = 10**9  # 不可达哨兵：最大总重 1000 × 800 = 8×10^5，远小于它


def pack(dp: list[list[int]], oxygen: int, nitro: int, weight: int) -> None:
    """放入一个气缸后的 0/1 转移：dp[i][j] 表示需求量被收拢到 (i, j) 时的最小总重。

    需求是"至少"语义，状态下标按 min(i+oxygen, 上限) 收拢——超过需求的部分不再区分。
    倒序枚举下标：目标状态只落在已访问过的位置，本气缸不会被二次使用；
    而当前状态在本轮尚未被写过，读到的始终是"前 i-1 个气缸"的结果。
    """
    need_o, need_n = len(dp) - 1, len(dp[0]) - 1
    for i in range(need_o, -1, -1):
        ni = min(i + oxygen, need_o)
        row, nxt = dp[i], dp[ni]
        for j in range(need_n, -1, -1):
            cost = row[j] + weight
            nj = min(j + nitro, need_n)
            if cost < nxt[nj]:
                nxt[nj] = cost


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    need_o, need_n = next(data), next(data)  # 需要的氧气、氮气量
    k = next(data)                           # 气缸个数

    dp = [[INF] * (need_n + 1) for _ in range(need_o + 1)]
    dp[0][0] = 0  # 什么都不带时两种气体都是 0，总重 0

    for _ in range(k):
        oxygen, nitro, weight = next(data), next(data), next(data)
        pack(dp, oxygen, nitro, weight)

    print(dp[need_o][need_n])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
55
56
57
58/**
 * 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-04 23:37
 * update_at: 2026-10-04 23:37
 */
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

const int MAXM = 21;  // 需要的氧气量上界
const int MAXN = 79;  // 需要的氮气量上界
const int MAXK = 1005;

// dp[i][j]：需求收拢状态 (i, j)（氧气 min(实际, m)、氮气 min(实际, n)）的最小总重
// 需求是"至少"语义，超过需求的气量不再区分，状态规模只有 (m+1)*(n+1)
// 最大总重 1000*800=8e5，int 足够；memset 0x3f 即为不可达哨兵
int dp[MAXM + 1][MAXN + 1];

ll need_o, need_n;           // 题目要求的氧、氮量，同时是状态表的两个维度
ll k;                        // 气缸个数
ll oxygen[MAXK], nitro[MAXK], weight[MAXK];  // 每个气缸的氧量、氮量、重量

// 放入第 cur 个气缸的 0/1 转移
// 目标下标 (min(i+a, m), min(j+b, n)) 不小于当前下标 (i, j)，
// 所以 i、j 都从大到小枚举：目标状态先写、当前状态后读，
// 本轮新写入的值不会被再次读到，每个气缸至多用一次（0/1 背包）
void pack(int cur) {
    for (ll i = need_o; i >= 0; --i) {
        ll ni = min(i + oxygen[cur], need_o);  // 氧气收拢：超出需求记为 need_o
        for (ll j = need_n; j >= 0; --j) {
            ll nj = min(j + nitro[cur], need_n);  // 氮气收拢：超出需求记为 need_n
            ll cost = dp[i][j] + weight[cur];
            if (cost < dp[ni][nj])
                dp[ni][nj] = cost;
        }
    }
}

int main() {
    scanf("%lld %lld", &need_o, &need_n);
    scanf("%lld", &k);
    for (int i = 1; i <= k; ++i)
        scanf("%lld %lld %lld", &oxygen[i], &nitro[i], &weight[i]);

    memset(dp, 0x3f, sizeof(dp));  // 不可达哨兵；最大总重 1000*800=8e5 远小于 0x3f3f3f3f
    dp[0][0] = 0;  // 什么都不带：两种气体均为 0，总重 0

    for (int i = 1; i <= k; ++i)
        pack(i);

    printf("%d\n", dp[need_o][need_n]);
    return 0;
}

复杂度

• 时间：$O(k \cdot m \cdot n)$——$k$ 个气缸各一轮、每轮 $(m+1)(n+1)$ 个状态。 最坏 $1000 \times 22 \times 80 = 1.76 \times 10^6$ 次内层操作，与 C++ 正解同阶， Python 下毫秒级完成。
• 空间：$O(m \cdot n)$，一张 $22 \times 80$ 的状态表，约 $1760$ 个整数。

总结

本题是"至少"语义的二维费用 0/1 背包。核心技巧是按需求上限收拢状态： 超出需求的气量不再区分，状态数被压到 $m \times n$；收拢后的转移只依赖收拢值本身， 于是普通二维背包的 $\min$ 转移即可覆盖所有子集。0/1 约束则靠倒序枚举实现—— 目标下标只增不减，倒序扫描让每个气缸至多进一次状态。遇到"至少/至多"型背包， 先想清楚哪些量超界后不再有信息量，把它们收拢掉，往往状态就降下来了。

图示解析

这张路线图串起本题从题面到答案的推导链：

1
2
3
4
5
6选气缸子集，氧 >= m 且氮 >= n，总重最小
`- 朴素：枚举 2^k 个子集 → k=1000 指数爆炸
   `- 观察①：需求是"至少"，超出部分无信息 → 状态收拢为 (min(x,m), min(y,n))
      `- 观察②：收拢值的转移只依赖收拢值本身 → 普通 min 转移即精确
         `- 0/1 约束：目标下标只增不减 → i、j 倒序枚举
            `- dp[0][0]=0 出发逐个气缸转移 → 答案 dp[m][n] = 249

第一个分叉说明朴素枚举失败的原因是"整体枚举子集"，没有可递推的状态； 观察①把二维状态压到 $m \times n$，观察②保证收拢不丢信息； 倒序枚举单独解决 0/1（与收拢互不干扰）；最后一行给出答案在状态表中的位置。