POJ 2184 Cow Exhibition

题意：给定n头牛的聪明指数S和幸福指数F，如果存在S的和TS>=0与F的和TF>=0同时成立时，

输出TS与TF的和的最大值sum，否则，输出0。

DP数组dp[i]表示当TS为i时右边TF最大值，这样就很巧妙的装化成01背包问题了。那最后的解就是满足条件的

dp[i+S]=max（dp[i+S],dp[i]+F）；

注意：由于TS可以为负，故可以把原点移动到pos=100000处

[cpp]
#include<iostream>
#include<cstdio>
using namespace std;
#define INF -999999999
#define N 200005
#define pos 100000
#define max(a,b) (a)>(b)?(a):(b)
int dp[N];
int minn,maxn;
int main()
{
   int n,i,j,s,t,ans;
   while(scanf("%d",&n)!=EOF)
   {
       for(i=0;i<N;i++) dp[i]=INF;
       dp[pos]=0;
       minn=maxn=pos;
      for(i=0;i<n;i++)
      {
         scanf("%d%d",&s,&t);
         if(s>0)
         {
            for(j=maxn;j>=minn;j--)
                dp[j+s]=max(dp[j+s],dp[j]+t);
            maxn=maxn+s;
         }
          else
          {
              for(j=minn;j<=maxn;j++)
                  dp[j+s]=max(dp[j+s],dp[j]+t);
             minn=minn+s;
          }
      }
      ans=0;
       for(i=pos;i<=maxn;i++)
         if(dp[i]>=0) ans=max(ans,i-pos+dp[i]);
         printf("%d\n",ans);
   }
   return 0;
}

补充：软件开发 , C++ ,