[USACO03FALL] Cow Exhibition G

GitHub跳转原题关系图返回列表

用偏移数组做 01 背包，记录智商和对应的最大情商，再在非负状态里取最大总和。

OJ: luogu

题目 ID: P2340

难度:普及

标签:动态规划01背包背包

创建: 2026-06-19 16:42

更新: 2026-10-07 10:45

前置题目
luogu P1734最大约数和B 主解在智商和状态上复用 A 教的「01 背包按转移方向倒序枚举、保证每件物品至多选一次」这一步（main.cpp 中 iq>=0 分支 for(s=hi;s>=lo;s--) 与 A 的 for(j=s;j>=i;--j) 同型，iq<0 分支才改为正序），并在其上叠加 A 未教的偏移量处理负智商和与双非负约束的收尾。luogu P8742[蓝桥杯 2021 省 AB] 砝码称重B 直接复用 A 教的「用偏移量把负数状态映射成非负下标」这一步：A 把差值 [-sum,sum] 平移 sum 得 offset=sum、dp[offset] 为初值，B 把智商和平移 OFFSET（main.cpp 里 OFFSET=400000、dp[OFFSET]=0），只是把可行性 dp 换成最大值 dp，并额外处理 iq 为负时正序枚举。
后置题目
luogu P4832珈百璃堕落的开始B 的差值背包直接复用 A 教的负数下标技巧：状态下标是可正可负的差值/智商和，靠偏移量换成非负下标，状态值存另一个量（A 存情商和、B 存总长度），且都按转移方向的正负决定倒序或正序枚举（B 的 main.cpp 里 diff>=0 倒序、diff<0 正序与 A 完全同型）；B 额外叠加的是 sin²+cos²=1 推出的配平建模与答案取一半。

目录

  1. 题意
  2. 思路
    1. 代码
    2. 复杂度
    3. 总结
    4. 一图流解析

    题意

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

    • 智商 iq_i
    • 情商 eq_i

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

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

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

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

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

    思路

    先看最直接的暴力：

    cpp
    #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 表示不选或选。递归先生成完整选择，叶子节点再检查两个和是否都非负，并统计最大总和。

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

    关键观察是：

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

    于是设：

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

    这张表说明状态定义：

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

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

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

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

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

    DP 公式

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

    dpOFFSET=0 dp_{OFFSET}=0

    处理一头智商为 aia_i、情商为 bib_i 的牛时：

    dps+ai=max⁡(dps+ai, dps+bi) dp_{s+a_i}=\max(dp_{s+a_i},\ dp_s+b_i)

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

    max⁡s⩾OFFSET, dps⩾0((s−OFFSET)+dps) \max_{s\geqslant OFFSET,\ dp_s\geqslant 0}\left((s-OFFSET)+dp_s\right)

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

    代码

    cpp
    #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)O(nS)，其中 S 是偏移数组的有效范围
    • 空间复杂度：O(S)O(S)

    总结

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

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

    一图流解析

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

    一图流解析