Spell Cards

시간 제한1초메모리 제한1024 MB

요약

일렬로 놓인 N장의 카드에서 인접한 두 카드를 합치며 그 합만큼 마력을 쓰고 두 카드 중 최댓값으로 대체할 때, 카드가 한 장 남을 때까지 쓰는 마력의 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

마리사는 바닥에 일렬로 늘어놓은 $N$ 장의 카드로 마법을 연습하고 있다. 왼쪽에서부터 $i$ 번째에 있는 $i$ 번 카드의 마력 소모량은 $a\_i$ 로 표현된다. 마리사가 $i$ 번 카드에 마법을 사용하기 위해서는 $a\_i$ 만큼의 마력을 소모해야 한다.

마리사는 인접한 두 카드를 골라서 마법을 시전한다. 이때 마리사는 고른 두 카드의 마력 소모량의 합만큼 마력을 소모한다. 이후 두 카드는 그 자리에서 하나로 합쳐지며, 새로 만들어진 카드의 마력 소모량은 이전 두 카드의 마력 소모량 중 최댓값이 된다. 이 과정은 카드가 단 하나만 남을 때까지 반복한다.

마리사는 소모하는 마력을 최소화하려 한다. 이때 마리사가 소모할 마력의 양을 구해주자!

입력

첫 번째 줄에 카드의 개수 $N$ 이 주어진다. $(1 \leq N \leq 400)$

두 번째 줄에 카드의 마력 소모량을 나타내는 정수 $a\_1, a\_2, \cdots, a\_N$ 가 공백으로 구분되어 주어진다. $(1 \leq a\_i \leq 10^9)$

출력

마리사가 소모하는 마력의 최솟값을 출력한다.

예제4

예제 1
입력
```
3
1 1 1
```
예상 출력
```
4
```
예제 2
입력
```
4
1 100 100 1
```
예상 출력
```
402
```
예제 3
입력
```
1
516
```
예상 출력
```
0
```
예제 4
입력
```
4
5 10 2 7
```
예상 출력
```
41
```