자두나무

 

//dp 점화식으로도 풀어보기 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_2240 {
 
    /*
     * 1에서 떨어질 때 받아먹으려면 내가 움직인 횟수가 짝수번,
 
        2에서 떨어질 때 홀수번이라고 생각했습니다.
        
        그외에는 받아먹지못하게 처리르헀고요.
        
     */
    static int t, w, max_eat;
    static int dp[][][] = new int[1001][32][3]; //t초에 i번 혹은 j번에 있을 때 자두의 최대개수 
    static int move[] = new int[1001];
    
    public static void main(String[] args) throws IOException{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        
        t = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
        
        for (int i = 1; i <= t; i++) {
            st = new StringTokenizer(br.readLine());
            move[i] = Integer.parseInt(st.nextToken()); //자두가 떨어지는 위치 
            
        }
        //input 
        
        //자두의 현재 위치는 1번에 있다. 
        
//        for (int i = 0; i < t; i++) {
//            dp[i][1] = 1 == move[i] ? 1 : 0; //같은 위치에 있을 때는 자두를 먹을 수 있다.  
//            //0 1 1 0 0 1 1 (1에만 계속 있었을 때 얻을 수 있는 최대 자두 개수)
//        }
//        
        for (int i = 1; i <= t; i++) {
            for (int j = 0; j <= w; j++) {
                dp[i][j][1] = dp[i][j][2] = -1;
            }
        }
        
        int ans = Math.max(moveJadoo(1, 0, 1) , moveJadoo(1, 1, 2));
        
        
        System.out.println(ans);
    }
    static int moveJadoo(int times, int move_cnt, int cur) {
        if (times > t || move_cnt > w ) { 
            return 0; //그만 움직임 
        }
        
        if (dp[times][move_cnt][cur] != -1) return dp[times][move_cnt][cur];
        //이미 했음 
        
        if (cur == move[times]) {
            //자두를 먹을 수 있다. 
            dp[times][move_cnt][cur] = 1;
        }
        else {
            //움직여야 먹을 수 있다. 
            dp[times][move_cnt][cur] = 0;
        }
        
        dp[times][move_cnt][cur] += Math.max(moveJadoo(times+1, move_cnt, cur), moveJadoo(times+1, move_cnt+1, 3-cur));
        
        return dp[times][move_cnt][cur];
    }
}