题目链接：
POJ 2184 Cow Exhibition
题意：
给n头牛，每头牛有两个属性:smart和fun,选出若干头牛使得这些牛的smart和fun之和最大,并且smart和与fun和均不为负。
每头牛的smart和fun可以为负。
分析：
01背包和滚动数组。
用dp[j]表示得到smart和为j时的fun和最大值。但是因为j可能为负，一开始我是用map，但是一直TLE。。。
后来改成二维表示：dp[j][0]:smart和为j(j>0)时的最大fun和，dp[j][1]:smart和为-j(j<0)时的最大fun和
初始化:
dp为最小，但是dp[0][0]=dp[0][1]=0;
状态转移方程需要注意要根据smart[i]的正负确定遍历的顺序，而且还要考虑j-smart[i]的正负。
最后再遍历扫一下dp[j][0]取最大就好了。
//600K 47MS
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int MAX_N=110;
const int MAX_M=110000;
const int inf=INT_MIN/3;int n;
int smart[MAX_N],fun[MAX_N],dp[MAX_M][2];int main()
{//freopen("Lin.txt","r",stdin);//freopen("Lout.txt","w",stdout);while(~scanf("%d",&n)){int max_sum=0,min_sum=0;for(int i=1;i<=n;i++){scanf("%d%d",&smart[i],&fun[i]);if(smart[i]>0) max_sum+=smart[i];else min_sum+=smart[i];}for(int j=1;j<=max(abs(min_sum),abs(max_sum))+1100;j++){dp[j][0]=dp[j][1]=inf;}dp[0][0]=dp[0][1]=0;for(int i=1;i<=n;i++){if(smart[i]>=0){for(int j=max_sum;j>=0;j--){if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[j][0]=max(dp[-(j-smart[i])][1]+fun[i],dp[j][0]);else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[j][0]=max(dp[j-smart[i]][0]+fun[i],dp[j][0]);//printf("i=%d j=%d dp[abs(j)][0]=%d\n",i,j,dp[abs(j)][0]);}for(int j=0;j>=min_sum;j--){if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[-j][1]=max(dp[-(j-smart[i])][1]+fun[i],dp[-j][1]);else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[-j][1]=max(dp[j-smart[i]][0]+fun[i],dp[-j][1]);//printf("i=%d j=%d dp[abs(j)][1]=%d\n",i,j,dp[abs(j)][1]);}}else {for(int j=min_sum;j<=0;j++){if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[-j][1]=max(dp[-(j-smart[i])][1]+fun[i],dp[-j][1]);else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[-j][1]=max(dp[j-smart[i]][0]+fun[i],dp[-j][1]);//printf("i=%d j=%d dp[abs(j)][1]=%d\n",i,j,dp[abs(j)][1]);}for(int j=0;j<=max_sum;j++){if(j-smart[i]<=0&&dp[-(j-smart[i])][1]!=inf) dp[j][0]=max(dp[-(j-smart[i])][1]+fun[i],dp[j][0]);else if(j-smart[i]>=0&&dp[j-smart[i]][0]!=inf) dp[j][0]=max(dp[j-smart[i]][0]+fun[i],dp[j][0]);//printf("i=%d j=%d dp[abs(j)][0]=%d\n",i,j,dp[abs(j)][0]);}}}int ans=0;for(int i=max_sum;i>=0;i--){if(dp[i][0]>=0){ans=max(ans,i+dp[i][0]);//printf("i=%d dp[i][0]=%d\n",i,dp[i][0]);}}printf("%d\n",ans);}return 0;
}