== 결과 ==
run-id	 user id	 프로그램 명	 결과	 언어	 경과 시간(초)	 코드 사이즈(byte)	 제출 시간
1373722	 zeropage	 treat	         accept	 C++	 0.17	         484	                 2014-07-17 06:08


== 설명 ==

 * 쿠키는 항상 가장 왼쪽이나 오른쪽부터 팔 수 있다. 즉 중간부터 팔 수 없음. 우리가 쿠키가 N개 있다고 할 때, j번째 쿠키를 판다면, 그것은 (1 ~ j-1)번째 쿠키가 팔려있는 상황이거나, (j + 1 ~ N)번째 쿠키가 팔려있는 상황이어야 함.
 * 우리가 쿠키를 지금 i개 판 상황일 때, 왼쪽에서 j개를 팔았다면, 오른쪽에서는 i - j개 팔려있는 상황임. 즉 전체 판 쿠키의 양과, 왼쪽부터 판 쿠키의 양을 알면 오른쪽부터 판 쿠키의 양은 정해짐. -> 고려해야 할 변수는 1. 지금까지 몇 개의 쿠키를 팔았는가, 2. 쿠키를 팔았다면, 왼쪽에서 몇 개 팔았는가. 이다.
 * 이를 고려하여 점화식을 구하면,

 * d(i, j) : 쿠키를 i개 팔았을 때, 왼쪽에서 다음 팔 수 있는 쿠키가 j번째 쿠키인 경우 얻을 수 있는 최대 돈의 양.

{{{
for(int i = 1; i<=n; i++){
	for(int j = 0; j<i; j++){
		d[i][j] = max(d[i][j], d[i-1][j] + (i * cookie[n - i + j]));
		d[i][j+1] = max(d[i][j+1], d[i-1][j] + (i * cookie[j]));
	}
}
}}}

== 소스 ==

{{{
#include<iostream>
using namespace std;
const int size = 2020;
int n;
int d[size][size], cookie[size];
int main(void)
{
	cin>>n;
	for(int i = 0; i<n; i++){
		cin>>cookie[i];
	}
	for(int i = 1; i<=n; i++){
		for(int j = 0; j<i; j++){
			d[i][j] = max(d[i][j], d[i-1][j] + (i * cookie[n - i + j]));
			d[i][j+1] = max(d[i][j+1], d[i-1][j] + (i * cookie[j]));
		}
	}
	int ans = 0;
	for(int i = 0; i<n; i++){
		ans = max(ans, d[n][i]);
	}
	cout<<ans;

	return 0;
}

}}}