Apple Catching

There are two apple trees, in each minute, one of the apple trees will drop an apple. You are given the tree number that drops apples in each minutes and you can which tree you are standing under to fetch the apple but the number of switching is limited. You are asked the maximum number of apples you can get.

The key to this problem is apply dynamic programming. Let $DP[i][j]$ denotes the maximum number of apples you can get after the $i$th minutes and you have switched $j$ times of position. Obviously when $j % 2 == 0$ you are in the first tree and otherwise you are in the second tree. So the iteration formular can be written as:

$$DP[i][j]=\max\left\{ DP[i-1][j-1],DP[i-1][j]\right\} +\begin{cases} 1 & under same tree\\ 0 & otherwise \end{cases}$$

Under same tree means the apple trees at the same tree as the tree you will be after $j$ times of switching.

import java.io.*;
import java.util.*;

public class AppleCatching {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt(), W = in.nextInt();
        int[] dp = new int[W + 1];
        for (int t = 1; t <= T; t++) {
            int tree = in.nextInt() - 1;
            for (int i = Math.min(W, t); i > 0; i--) {
                dp[i] = Math.max(dp[i] + ((i & 1) == tree ? 1 : 0), dp[i - 1] + 1);
            }
            dp[0] += (tree ^ 1);
        }
        int max = 0;
        for (int m : dp) {
            max = Math.max(max, m);
        }
        System.out.println(max);
    }
}