# POJ-2184 Cow Exhibition(01背包变形)

Cow Exhibition Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10949 Accepted: 4344 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.

```#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>

using namespace std;
#define MAX 99999999
int dp[200005];
int w[105];
int v[105];
int n;
int main()
{
int ans;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<=200000;i++)
dp[i]=-MAX;
ans=0;
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);

dp[100000]=0;
for(int i=1;i<=n;i++)
{
if(w[i]<0&&v[i]<0)
continue;
if(w[i]>0)
{
for(int j=200000;j>=w[i];j--)
{
if(dp[j-w[i]]!=-MAX)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
else
{
for(int j=w[i];j<=200000+w[i];j++)
{
if(dp[j-w[i]]!=MAX)
{
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
}
}
ans=-MAX;
for(int i=100000;i<=200000;i++)
{
if(dp[i]>=0)
ans=max(ans,dp[i]+i-100000);
}
printf("%d\n",ans);
}
return 0;
}```

479 篇文章43 人订阅

0 条评论

## 相关文章

### HDU----(4291)A Short problem(快速矩阵幂)

A Short problem Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32...

3516

### poj-------(2240)Arbitrage(最短路)

Arbitrage Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 156...

3768

### hdu---(1054)Strategic Game(最小覆盖边)

Strategic Game Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/3...

2835

### Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1542

### HDUOJ----（1031）Design T-Shirt

Design T-Shirt Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/327...

37013

### poj 1915 Knight Moves

Knight Moves Time Limit: 1000MS Memory Limit: 30000K Total Submissions:...

2143

### HDUOJ----Good Numbers

Good Numbers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

3086

"Let it Bead" company is located upstairs at 700 Cannery Row in Monterey, CA. As...

1052

### HDUOJ-----2399GPA

GPA Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

3574

### HDUOJ---1171

http://acm.hdu.edu.cn/showproblem.php?pid=1171 Big Event in HDU Time Limit: 1000...

2876