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
27
28
29
30
31
32
33
34
35
36
37
38 | #include <iostream>
using namespace std;
//pSum
//a[y][k] + sp(k+2, x)
// sp(k + 2, x) : maximum value which is sum of partial phases
int N, M;
int arr[101];
int cache[101][51];
bool tf[101][51];
int pSum[101];
int sp(int n, int m){
if(m == 0)
return 0;
if(n > N)
return -32768 * 100;
if(tf[n][m])
return cache[n][m];
tf[n][m] = true;
int & ret = cache[n][m];
ret = sp(n + 1, m);
for(int k = n; k<= N; k++){
ret = max(ret, sp(k + 2, m - 1) + pSum[k] - pSum[n - 1]);
}
return ret;
}
int main(){
cin >> N >> M;
for(int i = 1 ; i <= N; i++){
cin >> arr[i];
pSum[i] = arr[i] + pSum[i - 1];
}
cout << sp(1, M);
return 0;
}
|