| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 316 | 147 | 124 | 51.883% |
마리사는 바닥에 일렬로 늘어놓은 $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)$
마리사가 소모하는 마력의 최솟값을 출력한다.
3 1 1 1
4
마리사가 1ドル$번 카드와 2ドル$번 카드를 합치며 2ドル$의 마력을 소모한다. 이후 카드는 $[1, 1]$이 된다.
마리사가 마지막 남은 두 카드를 합치며 2ドル$의 마력을 소모한다. 마력의 총 소모량은 4ドル$이며, 이보다 마력을 적게 소모하는 방법은 존재하지 않는다.
4 1 100 100 1
402
마리사가 2ドル$번 카드와 3ドル$번 카드를 합치며 200ドル$의 마력을 소모한다. 이후 카드는 $[1, 100, 1]$이 된다.
마리사가 앞의 두 카드를 합치며 101ドル$의 마력을 소모한다. 이후 카드는 $[100, 1]$이 된다.
마리사가 마지막 남은 두 카드를 합치며 101ドル$의 마력을 소모한다. 마력의 총 소모량은 402ドル$이며, 이보다 마력을 적게 소모하는 방법은 존재하지 않는다.
1 516
0
이미 카드가 한 장이므로, 마리사는 마법을 사용할 필요가 없다.
4 5 10 2 7
41
마리사가 1ドル$번 카드와 2ドル$번 카드를 합치며 15ドル$의 마력을 소모한다. 이후 카드는 $[10, 2, 7]$이 된다.
마리사가 뒤쪽의 두 카드를 합치며 9ドル$의 마력을 소모한다. 이후 카드는 $[10, 7]$이 된다.
마리사가 마지막 남은 두 카드를 합치며 17ドル$의 마력을 소모한다. 마력의 총 소모량은 41ドル$이며, 이보다 마력을 적게 소모하는 방법은 존재하지 않는다.