2240번: 자두나무

https://www.acmicpc.net/problem/2240


$O(tw)$

dp[i][j]: i초에 j번 움직였을 때 먹을 수 있는 최대 자두 개수

#include<cstdio>
int dp[31], t, w, x;
int main() {
    scanf("%d%d", &t, &w);
    while (t--) {
        scanf("%d", &x);
        for (int i = w; i >= 0; i--) {
            if (i&&dp[i] < dp[i - 1]) dp[i] = dp[i - 1];
            dp[i] += x % 2 ^ i % 2;
        }
    }
    printf("%d", dp[w]);
    return 0;
}