题目

Description

"Fat and docile, big and dumb, they look so stupid, they aren't much
fun..."

• Cows with Guns by Dana Lyons

The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.

Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.

Input

• Line 1: A single integer N, the number of cows

• Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.

Output

• Line 1: One integer: the optimal sum of TS and TF such that both TS and TF are non-negative. If no subset of the cows has non-negative TS and non- negative TF, print 0.

Sample Input

5
-5 7
8 -6
6 -3
2 1
-8 -5

Sample Output

8

Hint

OUTPUT DETAILS:

Bessie chooses cows 1, 3, and 4, giving values of TS = -5+6+2 = 3 and TF
= 7-3+1 = 5, so 3+5 = 8. Note that adding cow 2 would improve the value
of TS+TF to 10, but the new value of TF would be negative, so it is not
allowed.

题解

每个牛有两个数值,这两个值有正有负,选取一部分牛,使得两个数值的总和最大,并且两个数值分别的和都是非负数

根据 选取一部分 ,可以转化成 对于一头牛,可以选择,也可以不选择 可以想到 背包问题

将其中一个数值看成体积,另一个看成价值,求取最大价值,然后将价值和对应的体积相加最大的就是结果

难点在于数值存在负数,有两种思路

• 使用 map 来模拟数组
• 使用指针偏移来使负数下标合理

使用指针偏移解决

然后就是直接的 01背包问题
需要注意的是,根据背包问题的证明,正数部分需要逆序,正数部分需要正序

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

typedef long long LL;

const int INF = 0x7FFFFFFF / 2;
const double eps = 1e-10;

const int maxn = 105;

const int Zero = 100 * 1000 + 5;
const int maxV = 2 * Zero;

int F[maxn],S[maxn];
int dp[maxV];
int *dp_zero = &dp[Zero];

int upv,lowv;

void ZeroOnePack(int cost,int weight) {
    if(cost > 0)
        for(int i = upv; i >= lowv; i--)
            dp_zero[i] = max(dp_zero[i],dp_zero[i - cost] + weight);
    else
        for(int i = lowv; i <= upv; i++)
            dp_zero[i] = max(dp_zero[i],dp_zero[i - cost] + weight);
}

bool Do() {
    int n;
    if(!(cin >> n))
        return false;

    for(int i = 1;i <= n;i++) {
        cin >> S[i] >> F[i];
        if(S[i] >= 0)
            upv += S[i];
        else
            lowv += S[i];
    }

    for(int i = 0;i < maxV;i++)
        dp[i] = -INF;
    dp_zero[0] = 0;

    for(int i = 1;i <= n;i++)
        ZeroOnePack(S[i],F[i]);

    int Max = 0;
    for(int i = 0;i < upv;i++) {
        if(dp_zero[i] >= 0)
            Max = max(dp_zero[i] + i,Max);
    }

    cout << Max << endl;
    return true;
}

int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    while(Do());

    return 0;
}