# 11090: 【原1090】小M的奶牛

### 题目描述

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

## 说明

（小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() {
for (int i = 0; i < n; ++i) {
}
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;
}