* Computer Science/Algorithm

baekjun 자두나무

soicem 2018. 11. 8. 21:32 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>

using namespace std;

int fallingApple[1001];
int cache[1001][31];
int T, W;
int catchApple(int n, int m){ // n : level, W : to 0
    if(n > T)
        return 0;
    if(m > W)
        return 0;
    if(cache[n][m] != -1)
        return cache[n][m];
    int & ret = cache[n][m];
    return ret = (fallingApple[n] == (m%2 + 1)) + max(catchApple(n + 1, m + 1), catchApple(n + 1, m));
}

int main(){
    memset(cache, -1, sizeof(cache));
    cin >> T >> W;
    for(int i = 1; i <= T; i++)
        cin >> fallingApple[i];
    cout << max(catchApple(1, 0), catchApple(1, 1));
    return 0;
}