题意

东海还需要至少 v 的体积才能填平。

现在有 n 块木石，每块木石有：

• 体积 k
• 运送它需要的体力 m

精卫还剩 c 点体力。每块木石最多使用一次，问：

• 如果能填平东海，最多还能剩多少体力
• 如果不能填平，输出 Impossible

思路

一句话本质：体力是容量，石头体积是价值。用 01 背包求出每种体力花费下的最大体积，找到第一个达到 $v$ 的最小体力花费。

先看最直接的暴力：

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
30import sys

data = list(map(int, sys.stdin.buffer.read().split()))
v_target, n, c = data[0], data[1], data[2]
stones = []
idx = 3
for _ in range(n):
    k, m = data[idx], data[idx + 1]
    idx += 2
    stones.append((k, m))

best_vol = 0
best_stamina = 0
for mask in range(1 << n):
    vol = 0
    stamina = 0
    for i in range(n):
        if mask >> i & 1:
            k, m = stones[i]
            vol += k
            stamina += m
    if stamina <= c:
        if vol > best_vol or (vol == best_vol and stamina < best_stamina):
            best_vol = vol
            best_stamina = stamina

if best_vol >= v_target:
    print(c - best_stamina)
else:
    print('Impossible')

brute.py 枚举 $2^n$ 种石头的选/不选组合，统计总体积和体力消耗。$n$ 最大 $10^4$，$2^{10000}$ 不可能。

暴力里的选择和 01 背包有什么对应关系？

每块石头只能用一次→0/1 物品。体力消耗 $m_i$ 是"重量"，石头体积 $k_i$ 是"价值"。暴力在做的事恰好在最大化体积，同时不超过体力上限。

但题目只要"至少达到 $v$"，不是"恰好等于 $v$"，怎么建模？

一旦体积已经 $\geqslant v$，再多出来的体积对答案没有额外收益——反正已经能填平东海了。所以可以把所有 $\geqslant v$ 的状态压缩到 $v$ 这一点上。转移到 $dp[\min(v, j+k)]$ 就实现了这个截断。

为什么要找最小体力花费，而不是直接求剩余体力？

题目问的是"填平后最多剩多少体力"，等价于在能达到 $v$ 的前提下体力花费最少。设 $dp_j$ 表示花 $j$ 体力能达到的最大体积（体积超过 $v$ 的都截到 $v$），从左到右扫描，第一个 $dp_j \geqslant v$ 的 $j$ 就是最小体力花费，答案 $= c - j$。

具体来说，设 $dp_j$ 表示花费 $j$ 体力能填的最大体积（超过目标 $v$ 时截断到 $v$）。处理第 $i$ 块石头（体积 $k_i$，消耗 $m_i$）时，倒序枚举体力 $j$：

然后对全体 $dp$ 值做 $\min(dp_j, v)$ 截断，保证状态只在 $0 \sim v$ 范围内。最后从小到大找第一个 $dp_j \geqslant v$ 的 $j$，输出 $c - j$。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXC = 10005;

int v_target, n, c;
// dp[j] 表示花费 j 体力能填的最大体积。
int dp[MAXC];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> v_target >> n >> c;

    fill(dp, dp + c + 1, 0);

    // 0/1 背包：体力是容量，石头体积是价值。
    for (int i = 1; i <= n; i++) {
        int k, m;
        cin >> k >> m;
        for (int j = c; j >= m; j--) {
            dp[j] = max(dp[j], dp[j - m] + k);
        }
    }

    // 找到最小的体力花费使填的体积 ≥ 目标。
    for (int j = 0; j <= c; j++) {
        if (dp[j] >= v_target) {
            cout << c - j << '\n';       // 剩余体力
            return 0;
        }
    }

    cout << "Impossible" << '\n';
    return 0;
}

复杂度

• 时间复杂度：$O(nv)$
• 空间复杂度：$O(v)$

总结

这题的关键不是普通的“最大价值背包”，而是：

• 至少达到一个阈值
• 并且让代价最小

遇到这种“达到目标就行、超过没有额外收益”的题时，要想到把状态截断到目标值，避免无意义地继续扩张状态空间。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。