题目链接： http://poj.org/problem?id=2566
题意：
每行给出si和fi，代表牛的两个属性，然后要求选出几头牛，是的则求出总S与总F的和，注意S与F都不能为负数
思路：
很明显的就是取与不取的问题，对于这类问题的第一想法就是背包，但是这道题目很明显与一般的背包不同，因为有负数，但是联想到以前也有这种将负数存入下标的情况，那就是将数组开大，换一种存法
我们用dp[i]存放每个s[i]能得到的最佳F，那么我们就可以根据s[i]的取值采取两种不同的01背包取法，在取完之后，然后再根据背包的有无再去求得最佳答案即可
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define pii pair<int, int>
typedef long long ll;
const int inf = 1044266559;
int dp[200005];
int main()
{int n, s[105], f[105];while(~scanf("%d", &n)){memset(dp, -63, sizeof(dp));dp[100000] = 0;for(int i = 1; i <= n; i++)scanf("%d%d", &s[i], &f[i]);for(int i = 1; i <= n; i++){if(s[i] < 0 && f[i] < 0) continue;if(s[i] > 0){for(int j = 200000; j >= s[i]; j--)if(dp[j - s[i]] > -inf)dp[j] = max(dp[j], dp[j-s[i]] + f[i]);}else{for(int j = 0; j <= 200000+s[i]; j++)if(dp[j-s[i]] > -inf)dp[j] = max(dp[j], dp[j-s[i]] + f[i]);}}int ans = -inf;for(int i = 100000; i <= 200000; i++)if(dp[i] >= 0)ans = max(ans, dp[i] + i - 100000);printf("%d\n", ans);}return 0;
}