O - 円環石板の結合 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MiB

配点 : 533 点

問題文

高橋君は、円形に並んだ N 枚の石板を持っている。石板には隣り合う順に 1, 2, \dots, N と番号が付けられており、石板 i の重さは A_i である。石板 N と石板 1 も隣り合っている。

高橋君は、石板が 1 枚になるまで以下の操作を繰り返す。

  • 円環上で隣り合っている 2 枚の石板を選び、 1 枚に結合する。結合によるコストは、選んだ 2 枚の石板の重さの合計に等しい。結合後にできる新しい石板の重さも、選んだ 2 枚の石板の重さの合計に等しい。新しい石板は元の 2 枚の石板を取り除いた位置に入り、元の 2 枚それぞれの反対側で隣り合っていた石板と新たに隣り合う。こうして、残りの石板は引き続き円環構造を保つ。

すべての操作で発生するコストの合計の最小値を求めてください。

制約

  • 2 \leq N \leq 3000
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

 N 
 A_1   A_2   \cdots   A_N
  • 1 行目には、石板の枚数を表す整数 N が与えられる。
  • 2 行目には、各石板の重さを表す整数 A_1, A_2, \dots, A_N がスペース区切りで与えられる。

出力

合計コストの最小値を 1 行で出力せよ。

入力例 1

4
3 1 4 1

出力例 1

18

入力例 2

3
10 20 30

出力例 2

90

入力例 3

8
7 2 9 4 6 3 8 5

出力例 3

132

入力例 4

30
12 45 7 23 89 34 56 78 11 90 5 67 38 42 19 73 61 29 84 16 50 99 3 27 64 8 71 36 14 52

出力例 4

6201

入力例 5

2
1000000000 1000000000

出力例 5

2000000000

Score : 533 pts

Problem Statement

Takahashi has N stone tablets arranged in a circle. The tablets are numbered 1, 2, \dots, N in adjacent order, and the weight of tablet i is A_i. Tablet N and tablet 1 are also adjacent.

Takahashi repeats the following operation until only one tablet remains.

  • Choose two tablets that are adjacent on the circle, and merge them into one. The cost of merging is equal to the sum of the weights of the two chosen tablets. The weight of the new tablet created by the merge is also equal to the sum of the weights of the two chosen tablets. The new tablet is placed at the position where the original two tablets were removed, and becomes adjacent to the tablets that were on the opposite sides of the original two tablets. In this way, the remaining tablets continue to maintain a circular structure.

Find the minimum possible total cost incurred across all operations.

Constraints

  • 2 \leq N \leq 3000
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \cdots A_N
  • The first line contains an integer N representing the number of tablets.
  • The second line contains integers A_1, A_2, \dots, A_N representing the weight of each tablet, separated by spaces.

Output

Print the minimum total cost in one line.

Sample Input 1

4
3 1 4 1

Sample Output 1

18

Sample Input 2

3
10 20 30

Sample Output 2

90

Sample Input 3

8
7 2 9 4 6 3 8 5

Sample Output 3

132

Sample Input 4

30
12 45 7 23 89 34 56 78 11 90 5 67 38 42 19 73 61 29 84 16 50 99 3 27 64 8 71 36 14 52

Sample Output 4

6201

Sample Input 5

2
1000000000 1000000000

Sample Output 5

2000000000