POJ.2184 Cow Exhibition

1.Problem
http://poj.org/problem?id=2184

2.Idea
dp[i][j]: Maximum sum of F, when using first i elements, and total S is j. Then, updating table like 0-1 knapsack problem. To save memory, re-use the table. Using map does not meet the time limit.

3.Source

 #define MAX_RANGE (100*2000+2)  
 #define offset 100000  
 int dp[2][MAX_RANGE];  
 int n;  
 int S[102];  
 int F[102];  
 int max(int x, int y) { return x>y ? x : y; }  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           cin >> S[i] >> F[i];  
      }  
      for (int i = 0; i < MAX_RANGE; i++) {  
           dp[0][i] = dp[1][i] = -INF;  
      }  
      int cur, next;  
      dp[0][offset] = 0;  
      for (int i = 0; i < n; i++) {  
           cur = i & 1; next = 1 - cur;  
           for (int i = 0; i < MAX_RANGE; i++) dp[next][i] = -INF;  
           for (int j = 0; j < MAX_RANGE; j++) {  
                if (dp[cur][j] != -INF) {
                     //not using i'th cow  
                     dp[next][j] = max(dp[next][j], dp[cur][j]);  

                     //using i'th cow
       dp[next][j + S[i]] = max(dp[next][j + S[i]], dp[cur][j] + F[i]);  
                }  
           }  
      }  
      int ans = 0;  
      for (int i = offset; i < MAX_RANGE; i++) {  
           if (dp[n&1][i] >= 0) ans = max(ans, i - offset + dp[n&1][i]);  
      }  
      cout << ans << endl;  
      return 0;  
 }