題意：有一些奶牛，他們有一定的s值和f值，這些值有正有負，最後讓保證s的和為非負且f的和為非負的情況下，s+f的最大值。
思路：背包問題，我們可以設dp[i][s]為前i頭牛的s值為s時f的最大值，這就轉化成了背包問題，即把s當成是體積，f當成是價值，而且可以成功的把二維轉化成一維。又因為有負數的情況，所以我們可以都加上一個值，全部轉化為正數。在處理負數的時候，循環順序需要改變一下，一個是01背包，一個是完全背包。即一個倒著循環，一個正著循環，最後取最大值即可。
代碼：
[cpp]
//2184
#include <iostream>
#include <cstdio>
#include <string.h>
#include <climits>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 110;
const int M = 100005;
struct cow{
int s,f;
}cc[N];
int dp[2*M];
int max(int a,int b){
return a>b?a:b;
}
int main(){
//freopen("1.txt","r",stdin);
int n;
while(scanf("%d",&n) != EOF){
for(int i = 0; i < n; ++i){
scanf("%d%d",&cc[i].s,&cc[i].f);
}
for(int i = 0; i < 2 * M ;++i)
dp[i] = INT_MIN;
dp[100000] = 0;
for(int i = 0; i < n; ++i){
if(cc[i].s >= 0){
for(int j = 2*M-1; j >= cc[i].s; --j){
if(dp[j - cc[i].s] > INT_MIN)
dp[j] = max(dp[j],dp[j - cc[i].s] + cc[i].f);
}
}
else{
for(int j = cc[i].s; j - cc[i].s < 2*M; ++j){
if(dp[j - cc[i].s] > INT_MIN)
dp[j] = max(dp[j],dp[j - cc[i].s] + cc[i].f);
}
}
}
int ans = INT_MIN;
for(int i = 100000; i < 2*M; ++i){
if(dp[i] >= 0)
ans = max(ans,dp[i] + i - 100000);
}
printf("%d\n",ans);
}
return 0;
}
作者：wmn_wmn
