백준 11052번 C++

 

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 1001;
int n;
int card[MAX];

int calmaxcost() {

	for (int i = 2; i <= n; i++) {
		for (int j = i - 1; j >= j / 2; j--) {
			card[i] = max(card[i], card[i - j]+ card[j]);
		}
	}
	return card[n];
}

int main(void) {
	cin >> n;

	for (int i = 1; i <= n; i++) 
		cin >> card[i];
	cout << calmaxcost() << endl;
	return 0;
}