baekjun 구간나누기

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