题目链接: https://vjudge.net/contest/537778#problem/I

题意

给出 n 头奶牛的情商 si 和智商 fi。从中选出若干头奶牛(可以不选)，在保证它们的智商之和与情商之和都不为负数的情况下，求最大的(情商和+智商和)。

(1≤N≤400, 1000≤Si​, Fi​≤1000)

思路

01背包。不能将奶牛的智商和加情商和作为价值，因为这样就没法判断正负了。

因为这里没有代价，所以考虑将智商和或情商和作为代价，另外一个做价值，然后最后求答案的时候找最大的代价对应的最大价值就可以了。

这里因为代价可能会从负数变成正数，所以要把整个 dp 数组开大一倍然后加上偏移值。然后因为要压维，所以01背包的枚举顺序也要注意，如果代价是负数就得正序枚举，如果是负数就得从逆序枚举，否则就变成完全背包了。另外如果情商和智商都是正数的话直接加上答案，小于等于0的直接扔掉就好了。

复杂度: O(n·n·1000)

呃呃呃好像差掉炸了诶。

代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          '\n';

const int maxN = 8e5+5;

struct st { int l; int r; };
long long dp[maxN];

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

  int n; std::cin >> n;
  std::vector<st> vl(n), vr(n);
  long long ret = 0;

  orep(i, 0, n) {
    int a, b; std::cin >> a >> b;
    if (a <= 0 && b <= 0) { continue; }
    if (a > 0 && b > 0) { ret += a + b; continue; }
    if (a > 0)  { vl.push_back({a, b}); }
    if (b > 0)  { vr.push_back({a, b}); }
  }

  memset(dp, -0x7f, sizeof(dp));
  dp[400000] = 0;
  orep(i, 0ul, vr.size()) {
    orep(j, 0, maxN-1+vr[i].l){
      dp[j] = std::max(dp[j-vr[i].l] + vr[i].r, dp[j]);
    }
  }
  orep(i, 0ul, vl.size()) {
    for(int j = maxN-1; j >= vl[i].l; --j) {
      dp[j] = std::max(dp[j-vl[i].l] + vl[i].r, dp[j]);
    }
  }
  long long max = 0;
  orep(i, 400000, maxN) {
    if (dp[i] >= 0) {
      max = std::max(dp[i] + i - 400000, max);
    }
  }
  std::cout << max + ret;

  return 0;
}