Skip to content

11090: 【原1090】小M的奶牛

题目

题目描述

author: 寿鹤鸣 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1090

Description

小M的奶牛们想向社会证明其实他们是聪明而且风趣的。

为此,小M筹备了一个专门展览奶牛的博览会,她已经对\( N (1 \leq N \leq 100) \)头奶牛进行了面试,确定了每 头奶牛的聪明指数\( Si (−1000 \leq Si \leq 1000) \) 和风趣指数\( Fi (−1000 \leq Fi \leq 1000) \)。

小M需要决定让哪些奶牛上博览会。

设总聪明指数TS为各奶牛聪明指数Si的和,总风趣指数TF为各奶牛风趣指数Fi的和。小M想使TS与TF的和最大,同时她希望这两个值不要小于零(因为她要证明奶牛们是出色的,负的TS或TF会造成负面的效果)。请帮助小M求出TS与TF在非负条件下的最大和。

Input Format

第一行:一个整数N,表示奶牛的数量

第二行到第N + 1行:每行两个用空格分开的整数:Si和Fi,分别代表每头奶牛的聪明指数和风趣指数

Output Format

第一行:单独一个整数,表示在TS和TF非负条件下的最大和。如果无解,则输出 0

说明

样例解释

(小M可以选择 1,3,4 号奶牛,此时 TS = −5 + 6 + 2 = 3,TF = 7 − 3 + 1 = 5, 总和为8。注意如果加入 2 号奶牛可以使总和 提升到10,不过TF变负了,而这是不允许的。)

Sample Input

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

Sample Output

8

FineArtz's solution

/* 小M的奶牛 */
#include <iostream>
using namespace std;

const int DEL = 100000;
const int INF = 2000000000;

int main(){
    int n;
    int s[105], f[105];
    int a[100005 + DEL];
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> s[i] >> f[i];
    }
    for (int i = 0; i <= 100000 + DEL; ++i)
        a[i] = -INF;
    a[DEL] = 0;
    for (int i = 1; i <= n; ++i){
        if (s[i] > 0){
            for (int j = 100000 + DEL; j >= s[i]; --j)
                if (a[j - s[i]] != -INF)
                    a[j] = max(a[j], a[j - s[i]] + f[i]);
        }
        else{
            for (int j = 0; j <= s[i] + 100000 + DEL; ++j)
                if (a[j - s[i]] != -INF)
                    a[j] = max(a[j], a[j - s[i]] + f[i]);
        }
    }
    int ans = 0;
    for (int i = 0; i <= 100000; ++i)
        if (a[i + DEL] >= 0)
            ans = max(ans, a[i + DEL] + i);
    cout << ans << endl;
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstdio>
#include <climits>
#define MAX_S 100020
#define MAX_N 105
using namespace std;
int n, ans;
int s[MAX_N], f[MAX_N];
int dp[MAX_S << 1];
inline int read() {
    char ch = getchar(); int flag = 1, res = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
int main() {
    n = read();
    for (int i = 0; i < n; ++i) {
        s[i] = read(); f[i] = read();
    }
    for (int i = 0; i < (MAX_S << 1); ++i) dp[i] = INT_MIN;
    dp[MAX_S] = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] <= 0 && f[i] <= 0)
            continue;
        if (s[i] > 0) {
            for (register int j = (MAX_S << 1) - 1; j >= s[i]; --j)
                if (dp[j - s[i]] > INT_MIN && dp[j - s[i]] + f[i] > dp[j])
                    dp[j] = dp[j - s[i]] + f[i];
        }
        else {
            for (register int j = 0; j < (MAX_S << 1) + s[i]; ++j)
                if (dp[j - s[i]] > INT_MIN && dp[j - s[i]] + f[i] > dp[j])
                    dp[j] = dp[j - s[i]] + f[i];
        }
    }
    for (register int i = MAX_S; i < (MAX_S << 1); ++i)
        if (dp[i] >= 0)
            ans = max(ans, dp[i] + i - MAX_S);
    printf("%d\n", ans);
    return 0;
}