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;
}
|