[USACO03FALL] Cow Exhibition G

题意

有 n 头奶牛，每头奶牛有两个属性：

智商 iq_i
情商 eq_i

可以选择其中一些奶牛参加展览。要求最后选出的奶牛满足：

智商和不小于 0
情商和不小于 0

在满足条件的前提下，希望 智商和 + 情商和 尽量大。

这张表把题意翻成了背包模型：

原题对象	背包含义
一头奶牛	一个 0/1 物品
智商	需要偏移的状态维度
情商	状态值
最终要求	选择后两个和都非负

思路

先看最直接的暴力：

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

int n;
vector<int> iq, eq;
vector<int> choose_cow; // choose_cow[i] = 0/1，表示第 i 头奶牛不选/选
int answer = 0;

void calc_sum(int &sum_iq, int &sum_eq) {
    sum_iq = 0;
    sum_eq = 0;
    for (int i = 0; i < n; i++) {
        if (choose_cow[i] == 1) {
            sum_iq += iq[i];
            sum_eq += eq[i];
        }
    }
}

bool check() {
    int sum_iq, sum_eq;
    calc_sum(sum_iq, sum_eq);
    return sum_iq >= 0 && sum_eq >= 0;
}

int calc_answer() {
    int sum_iq, sum_eq;
    calc_sum(sum_iq, sum_eq);
    return sum_iq + sum_eq;
}

// dfs_choose 只负责枚举完整 01 序列。
void dfs_choose(int dep) {
    if (dep == n) {
        if (check()) {
            int value = calc_answer();
            if (answer < value) answer = value;
        }
        return;
    }

    // 第 dep 头奶牛的 01 选择：0 不选，1 选。
    for (int i = 0; i <= 1; i++) {
        choose_cow[dep] = i;
        dfs_choose(dep + 1);
    }
}

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

    cin >> n;
    iq.resize(n);
    eq.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> iq[i] >> eq[i];
    }

    choose_cow.assign(n, 0);
    dfs_choose(0);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每头牛看成一个 01 选择：choose_cow[i] = 0/1 表示不选或选。递归先生成完整选择，叶子节点再检查两个和是否都非负，并统计最大总和。

这个做法正确，但复杂度很高，只适合小数据验证。

关键观察是：

智商和可能为负，所以不能直接把它当普通下标。
只要把智商和整体向右平移一个足够大的偏移量，就能把负数状态变成非负下标。
对于每个智商和，我们只需要记录能得到的最大情商和。

于是设：

dp[s] 表示智商和为 s - OFFSET 时，能得到的最大情商和

这张表说明状态定义：

状态	含义
`dp[s]`	智商和为 `s - OFFSET` 时的最大情商和

处理一头奶牛 (iq_i, eq_i) 时：

不选它：状态保持不变
选它：智商和加 iq_i，情商和加 eq_i

如果 iq_i 非负，智商和会向右移动，倒序枚举；如果 iq_i 为负，智商和会向左移动，正序枚举。

最后只在智商和非负、情商和非负的状态里，取 智商和 + 情商和 的最大值。

DP 公式

设偏移量为 $OFFSET$ ， $dp_s$ 表示智商和为 $s-OFFSET$ 时能得到的最大情商和。初始化：

dp_{OFFSET}=0

处理一头智商为 $a_i$ 、情商为 $b_i$ 的牛时：

dp_{s+a_i}=\max(dp_{s+a_i},\ dp_s+b_i)

最终只在智商和、情商和都非负的状态中取最大：

\max_{s\geqslant OFFSET,\ dp_s\geqslant 0}\left((s-OFFSET)+dp_s\right)

公式解释：智商和可能为负，所以用偏移量把它变成数组下标。dp_s 保存这个智商和下能达到的最大情商和，最后只允许智商和、情商和都非负的状态参与答案。

代码

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 OFFSET = 400000;
const int LIMIT = OFFSET * 2;
const int NEG_INF = -1000000000;

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

    int n;
    cin >> n;

    vector<int> iq(n), eq(n);
    for (int i = 0; i < n; i++) {
        cin >> iq[i] >> eq[i];
    }

    // dp[s]：智商和为 s - OFFSET 时，能得到的最大情商和。
    vector<int> dp(LIMIT + 1, NEG_INF);
    dp[OFFSET] = 0;

    int lo = OFFSET, hi = OFFSET;
    for (int i = 0; i < n; i++) {
        int a = iq[i];
        int b = eq[i];

        if (a >= 0) {
            for (int s = min(hi, LIMIT - a); s >= lo; s--) {
                if (dp[s] == NEG_INF) continue;
                dp[s + a] = max(dp[s + a], dp[s] + b);
            }
            hi = min(LIMIT, hi + a);
        } else {
            for (int s = lo; s <= hi; s++) {
                if (dp[s] == NEG_INF) continue;
                dp[s + a] = max(dp[s + a], dp[s] + b);
            }
            lo = max(0, lo + a);
        }
    }

    int answer = 0;
    for (int s = OFFSET; s <= hi; s++) {
        if (dp[s] >= 0) {
            answer = max(answer, dp[s] + s - OFFSET);
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

时间复杂度： $O(nS)$ ，其中 S 是偏移数组的有效范围
空间复杂度： $O(S)$

总结

这题的核心是“负数权值要偏移”。

把智商和作为状态下标后，情商和只需要作为状态值保存。这样一来，题目就变成了一个带负数权值的 0/1 背包问题。

一图流解析

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