2240 자두나무

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int main() {
    int t, w;
    scanf("%d %d", &t, &w);
 
    int plum[1001] = { 0 };
    for (int i = 1; i <= t; i++)
        scanf("%d", &plum[i]);
 
    int dp[1001][31] = { 0 };
    for (int i = 1; i <= t; i++) {
        for (int j = 0; j <= w; j++) {
            if(j>=1)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]);
            else
                dp[i][j] = dp[i - 1][j];
 
            if ((j % 2 == 0 && plum[i] == 1) || (j % 2 == 1 && plum[i] == 2))
                dp[i][j]++;
        }
    }
 
    int maxPlum = -1;
    for (int i = 0; i <= w; i++)
        if (maxPlum < dp[t][i])
            maxPlum = dp[t][i];
 
    printf("%d", maxPlum);    
}

할만하다!