精卫填海

题意

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

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

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

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

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

思路

先看最直接的暴力：

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
55
56
57
58
59
60
61
62
63
64
65
66// brute.cpp：小数据暴力解，使用 01 序列枚举每块木石选或不选。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int need_volume;          // 至少需要填平的体积
int n;                    // 木石数量
int stamina_limit;        // 剩余体力
int volume_gain[MAXN];    // 木石体积
int stamina_cost[MAXN];   // 木石体力消耗
int choose_stone[MAXN];   // choose_stone[i] = 0/1，表示第 i 块木石不选/选
int best_cost;            // 达到目标体积时的最小体力消耗

bool check() {
    int sum_volume = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_stone[i] == 1) sum_volume += volume_gain[i];
    }
    return sum_volume >= need_volume;
}

int calc_cost() {
    int sum_cost = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_stone[i] == 1) sum_cost += stamina_cost[i];
    }
    return sum_cost;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_cost();
            if (best_cost > value) best_cost = value;
        }
        return;
    }

    // 第 dep 块木石的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_stone[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> need_volume >> n >> stamina_limit;
    for (int i = 1; i <= n; i++) {
        cin >> volume_gain[i] >> stamina_cost[i];
    }

    best_cost = 0x3f3f3f3f;
    dfs_choose(1);

    if (best_cost > stamina_limit) {
        cout << "Impossible\n";
    } else {
        cout << stamina_limit - best_cost << '\n';
    }

    return 0;
}

brute.cpp 把每块木石看成一个 01 选择：choose_stone[i] = 0/1 表示不选或选。递归先生成完整选择，叶子节点再检查总体积是否至少达到 v，并统计最小体力消耗。

这个做法显然正确，但复杂度是 $O(2^n)$ ，只能做小数据验证。

这题本质上是 0/1 背包：每块木石只能用一次。

不过它不是“价值最大化”，而是：

总体积至少达到 v
让总消耗体力最小

关键观察是：一旦体积已经达到或超过 v，再多出来的体积对答案没有区别。

因此设：

dp[j] 表示达到体积 j 所需的最小体力

这里 j 只开到 v。如果加入一块木石后体积超过 v，就统一记成 v：

nxt = min(v, j + k)
dp[nxt] = min(dp[nxt], dp[j] + m)

这样就把“至少达到 v”的问题变成了“达到 v 这个截断状态的最小代价”。

状态表

这张表说明状态的含义：

状态	含义
`dp[j]`	达到体积 `j` 所需的最小体力

其中 j = v 不表示恰好等于 v，而是表示“已经达到或超过 v”。这就是本题最关键的截断思想。

最后如果 dp[v] > c，说明体力不够；否则答案就是 c - dp[v]。

DP 公式

设 $dp_j$ 表示达到体积 $j$ 所需的最小体力，并把所有超过目标体积 $v$ 的状态截断到 $v$ 。初始化：

dp_0=0,\quad dp_j=+\infty\ (j>0)

处理一块体积为 $k_i$ 、体力消耗为 $m_i$ 的木石时：

dp_{\min(v,j+k_i)}=\min\left(dp_{\min(v,j+k_i)},\ dp_j+m_i\right)

若 $dp_v>c$ 则无法填海，否则答案为：

c-dp_v

公式解释：题目只关心体积是否至少达到目标，因此超过 v 的体积统一压到状态 v。转移中的 min(v,j+k_i) 表示“已经够了”和“刚好够”没有区别。

代码

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

const int MAXN = 10005;
const int MAXV = 10005;
const int INF = 0x3f3f3f3f;

int need_volume;          // 至少需要填平的体积
int n;                    // 木石数量
int stamina_limit;        // 剩余体力
int volume_gain[MAXN];    // 第 i 块木石的体积
int stamina_cost[MAXN];   // 第 i 块木石需要的体力
int dp[MAXV];             // dp[j] = 达到体积 j (j 被截断到 need_volume) 所需的最小体力

void read_input() {
    cin >> need_volume >> n >> stamina_limit;
    for (int i = 1; i <= n; i++) {
        cin >> volume_gain[i] >> stamina_cost[i];
    }
}

void solve() {
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = need_volume; j >= 0; j--) {
            if (dp[j] == INF) {
                continue;
            }
            int nxt = j + volume_gain[i];
            if (nxt > need_volume) {
                nxt = need_volume;
            }
            dp[nxt] = min(dp[nxt], dp[j] + stamina_cost[i]);
        }
    }

    if (dp[need_volume] > stamina_limit) {
        cout << "Impossible\n";
    } else {
        cout << stamina_limit - dp[need_volume] << '\n';
    }
}

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

    read_input();
    solve();

    return 0;
}

复杂度

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

总结

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

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

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

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析