레이팅 미적용설명
\(N\)개의 풍선이 일렬로 있고, \(i\)번째 풍선에는 수 \(a_i\)가 적혀 있다. 풍선을 하나씩 터뜨린다. 풍선 \(i\)를 터뜨리면 \(L \cdot a_i \cdot R\) 만큼의 동전을 얻는데, 여기서 \(L\)과 \(R\)은 아직 터지지 않은, \(i\)의 바로 왼쪽과 오른쪽에 있는 풍선의 수이다(양 끝 바깥의 없는 이웃은 \(1\)로 간주한다). 모든 풍선을 최적의 순서로 터뜨려 얻을 수 있는 최대 동전 수를 구하시오.
제약
입력 형식
첫 줄에 \(N\) (\(1 \le N \le 60\))이 주어진다. 둘째 줄에 \(N\)개의 정수 \(a_i\) (\(0 \le a_i \le 100\))가 주어진다.
출력 형식
최대 동전 수를 출력한다.
예제 1
입력
4
3 1 5 8
출력
167
예제 2
입력
2
1 5
출력
10
예제 3
입력
1
5
출력
5
문제 정보
riseoj 작성
출처 RiseOJ Basics
태그