T2-10 Cow Exhibition

题意理解

选择若干奶牛，使得智商和 $\geq 0$，情商和 $\geq 0$，最大化智商与情商的总和。

---

思路分析

把智商作为"费用"，情商作为"价值"，转化为01背包。

设 $dp[j]$ 表示智商和恰好为 $j$ 时，情商和的最大值。

由于智商可能为负，需要做偏移。智商范围 $[-1000, 1000]$，$N \leq 400$，所以智商和范围 $[-400000, 400000]$。设偏移量 $OFFSET = 400000$。

状态转移（关键点）：

• 若 $s[i] \geq 0$：逆序枚举（普通01背包）
• 若 $s[i] < 0$：正序枚举（保证每个物品只选一次）

边界条件：

• $dp[OFFSET] = 0$：不选任何牛，智商和为0，情商和为0
• 其他初始化为负无穷

答案： 对于所有 $j \geq 0$ 且 $dp[j + OFFSET] \geq 0$，最大化 $j + dp[j + OFFSET]$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int OFFSET = 400005;       // 偏移量，处理负数下标
const int MAXM = OFFSET * 2 + 5; // 数组大小
const int INF = 0x3f3f3f3f;      // 无穷大

int n;              // 奶牛数量
int s[405], f[405]; // 每头牛的智商和情商
int dp[MAXM];       // dp[j+OFFSET]表示智商和为j时的最大情商和

int main() {
    cin >> n;  // 读入奶牛数量
    
    for (int i = 1; i <= n; i++) {  // 读入每头牛的智商和情商
        cin >> s[i] >> f[i];
    }
    
    for (int i = 0; i < MAXM; i++) {  // 初始化为负无穷
        dp[i] = -INF;
    }
    dp[OFFSET] = 0;  // 边界：智商和为0时，情商和为0
    
    for (int i = 1; i <= n; i++) {  // 枚举每头牛
        if (s[i] >= 0) {  // 智商非负，逆序枚举
            for (int j = OFFSET * 2; j >= s[i]; j--) {
                if (dp[j - s[i]] > -INF) {  // 前一个状态可达
                    dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
                }
            }
        } else {  // 智商为负，正序枚举
            for (int j = 0; j <= OFFSET * 2 + s[i]; j++) {
                if (dp[j - s[i]] > -INF) {  // 前一个状态可达
                    dp[j] = max(dp[j], dp[j - s[i]] + f[i]);
                }
            }
        }
    }
    
    int ans = 0;  // 答案，至少为0（可以不选任何牛）
    for (int j = OFFSET; j <= OFFSET * 2; j++) {  // 枚举智商和>=0的情况
        if (dp[j] >= 0) {  // 情商和也>=0
            ans = max(ans, j - OFFSET + dp[j]);  // 更新答案
        }
    }
    
    cout << ans << endl;  // 输出答案
    return 0;
}