T3：最大子集
本题是 01背包 的变种题
记 dp[i] 表示选到的奶牛的智商总和为 \(i\) 时对应的情商总和的最大值
这里由于 \(x\) 可能是负数，所以需要将 \(i\) 向后偏移 \(3e5\)
特别地，在转移时，当 \(x>0\) 时，倒序枚举 \(i\)；而当 \(x < 0\) 时，则需要正序枚举 \(i\)
理由也很简单，是为了保证 \(dp\) 转移的无后效性
原题：[USACO03FALL]Cow Exhibition G
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmax(int& x, int y) { if (x < y) x = y; }
int dp[600005];
int main() {
int n;
cin >> n;
memset(dp, 0xcf, sizeof dp);
const int S = 300000, M = S*2;
dp[S] = 0;
rep(i, n) {
int x, y;
cin >> x >> y;
if (x >= 0) {
for (int j = M; j >= x; --j) {
chmax(dp[j], dp[j-x]+y);
}
}
else {
for (int j = 0; j-x <= M; ++j) {
chmax(dp[j], dp[j-x]+y);
}
}
}
int ans = 0;
for (int i = S; i <= M; ++i) {
if (dp[i] >= 0) {
chmax(ans, i+dp[i]-S);
}
}
cout << ans << '\n';
return 0;
}