5 倍经验日

题意

有 $n$ 个好友（ $n \leqslant 10^3$ ），手上有 $x$ 瓶药水（ $x \leqslant 10^3$ ）。对第 $i$ 个好友：

失败时获得经验 $lose_i$
胜利时获得经验 $win_i$ ，需要消耗至少 $use_i$ 瓶药水

每瓶药水只能用一次。求最大经验值 $s$ ，输出 $5s$ 。

原题对象	背包含义
一个好友	一个物品
药水消耗 $use_i$	物品重量
失败经验 $lose_i$	不选时的"保底收益"
胜利经验 $win_i$	选时的收益
药水总数 $x$	背包容量

思路

一句话本质： 01 背包变体——每个好友不打也有收益（ $lose_i$ ），打需要消耗药水获得更多收益（ $win_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
55
56
57
58
59
60
61
62
63
64
65
66
67// brute.cpp：小数据暴力解，使用 01 序列枚举每个好友打或不打。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;              // 好友数量
int x;              // 药水数量
int lose_exp[MAXN]; // 失败时获得的经验
int win_exp[MAXN];  // 胜利时获得的经验
int need[MAXN];     // 打过至少需要的药水数量
int choose_friend[MAXN]; // choose_friend[i] = 0/1，表示不打/打第 i 个好友
long long best_answer;   // 最大经验值

// 检查当前选择方案的总药水消耗是否不超过 x
bool check() {
    int total_need = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_friend[i] == 1) total_need += need[i];
    }
    return total_need <= x;
}

// 计算当前选择方案的总经验
long long calc_answer() {
    long long total = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_friend[i] == 1)
            total += win_exp[i];
        else
            total += lose_exp[i];
    }
    return total;
}

// 01 序列递归枚举
void dfs(int dep) {
    if (dep == n + 1) {
        if (check()) {
            long long cur = calc_answer();
            if (best_answer < cur) best_answer = cur;
        }
        return;
    }

    // 第 dep 个好友：0 不打，1 打
    for (int i = 0; i <= 1; i++) {
        choose_friend[dep] = i;
        dfs(dep + 1);
    }
}

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

    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> lose_exp[i] >> win_exp[i] >> need[i];
    }

    best_answer = 0;
    dfs(1);

    cout << 5LL * best_answer << '\n';
    return 0;
}

这个暴力用 01 序列枚举每个好友打或不打，叶子节点检查总药水消耗是否超限，并统计总经验。复杂度 $O(2^n)$ ，只适合小数据验证。

和标准 01 背包相比，这题多出了什么？

标准 01 背包："不选"收益为 0，"选"收益为 $value_i$ 。本题："不打"收益为 $lose_i$ ，"打"收益为 $win_i$ ——不选也有收益。

不选也有收益，对 DP 状态有什么影响？

在 01 背包的一维倒序框架里，每轮处理物品时，无论如何都会经历"不选"的路径。所以可以把"不打"收益直接加到当前状态上： $dp[j] = dp[j] + lose_i$ （表示无论药水够不够，都不打这个好友，拿走失败经验）。然后再考虑"打"的转移：如果 $j \geqslant use_i$ ，尝试 $dp[j] = \max(dp[j], dp[j-use_i] + win_i)$ 。

为什么 $dp[j-use_i]$ 在 $j$ 倒序枚举时是安全的？

倒序枚举 $j$ ，计算 $dp[j]$ 时 $dp[j-use_i]$ 还保留着上一轮（前 $i-1$ 个好友）的旧值，没有被本轮更新覆盖。这保证了每个好友最多只打一次。

为什么 dp 需要用 long long？

$win_i$ 和 $lose_i$ 最大可达 $10^6$ ， $n = 10^3$ ，总经验可达 $10^9$ 级别，超出 int 范围（ $2^{31}-1 \approx 2.1 \times 10^9$ 尚可，但加上中间累加使用 long long 更安全）。

DP 公式

设 $dp_j$ 表示使用不超过 $j$ 瓶药水的最大经验值。处理第 $i$ 个好友时（ $j$ 倒序）：

dp_j = \max(dp_j + lose_i,\ dp_{j-use_i} + win_i) \quad (j \geqslant use_i)

对于 $j < use_i$ ，只有不打一种选择：

dp_j = dp_j + lose_i

最终输出 $5 \times dp_x$ 。

样例 DP 表格

以官方样例为例： $n=6, x=8$ ，好友数据 $(lose, win, use)$ 依次为 $(21,52,1), (21,70,5), (21,48,2), (14,38,3), (14,36,1), (14,36,2)$ 。

处理好友	参数	$dp[8]$ 变化说明
初始	—	$dp[0 \sim 8] = 0$
好友 1	(21,52,1)	每个 $j$ 先 $+21$ （不打）， $j \geqslant 1$ 时尝试 $dp[j-1]+52$ 。例如 $dp[8]=\max(0+21,0+52)=52$
好友 2	(21,70,5)	$j<5$ 只能 $+21$ ； $j \geqslant 5$ 尝试 $dp[j-5]+70$ 。例如 $dp[8]=\max(52+21, dp[3]+70)$
好友 3	(21,48,2)	…
好友 4	(14,38,3)	…
好友 5	(14,36,1)	…
好友 6	(14,36,2)	…

最终 $dp[8] = 212$ （不展示完整逐行表避免冗长；转移逻辑与标准 01 背包一致，区别仅在于每一行先加 $lose_i$ ）。

答案 $5 \times 212 = 1060$ 。

代码

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

const int MAXN = 1005;
const int MAXX = 1005;

int n;                // 好友数量
int x;                // 药水数量
int lose_exp[MAXN];    // 失败时获得的经验
int win_exp[MAXN];     // 胜利时获得的经验
int need[MAXN];        // 打过至少需要的药水数量
long long dp[MAXX];    // dp[j] = 使用 j 瓶药水能获得的最大经验值

void read_input() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> lose_exp[i] >> win_exp[i] >> need[i];
    }
}

void solve() {
    memset(dp, 0, sizeof(dp));

    for (int i = 1; i <= n; i++) {
        // 倒序枚举药水数，保证每个好友最多只打一次。
        // 使用 long long 防止中间结果溢出。
        for (int j = x; j >= 0; j--) {
            // 不打这个好友 → 获得失败经验
            dp[j] = dp[j] + lose_exp[i];
            // 打这个好友 → 比较胜利经验是否更大
            if (j >= need[i]) {
                // dp[j - need[i]] 是本轮更新前的值，即上一轮的结果
                dp[j] = max(dp[j], dp[j - need[i]] + win_exp[i]);
            }
        }
    }

    // 题目要求输出 5 × 最大经验
    cout << 5LL * dp[x] << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(nx)$
空间复杂度： $O(x)$

总结

这题是 01 背包的一个常见变体——每个物品"不选"也有收益。处理方法是在每轮倒序转移前，给所有状态加上 $lose_i$ ，再考虑选的情况。这种"保底收益+额外收益"的模式在竞赛中经常出现。

目录

题意

思路

DP 公式

样例 DP 表格

代码

复杂度

总结