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; 
}