POJ.2385 Apple Catching

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

2. Idea
define a dp like this, dp[i][j]: the max apple catching number when equal or under j movement and until i'th minut.


3.Source

 int t, w;  
 int a[1003];  
 int dp[1003][33];  
 int main()  
 {  
      cin >> t >> w;  
      for (int i = 0; i < t; i++) cin >> a[i];  
      if (a[0] == 1) {  
           dp[0][0] = 1;  
           dp[0][1] = 0;  
      }  
      else {  
           dp[0][0] = 0;  
           dp[0][1] = 1;  
      }  
      for (int i = 1; i < t; i++) {  
           for (int j = 0; j <= w; j++) {  
                // 0 movement case  
                if (j == 0) {   
                     dp[i][j] = dp[i - 1][j];  
                     if (a[i] == 1) dp[i][j]++;  
                     continue;  
                }  
                // take best of no move / move   
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);  
                if ((a[i] == 1 && j % 2 == 0) || (a[i] == 2 && j % 2 == 1)) dp[i][j]++;  
           }  
      }  
      int ans = 0;  
      for (int j = 0; j <= w; j++) ans = max(ans, dp[t - 1][j]);  
      cout << ans << endl;  
      return 0;  
 }