← 返回题目列表

AtCoder · awc0100_o

O. 圆形片材的连接

中文机器翻译题面 查看原题

分数: 533 分

问题陈述

高桥有 N 石碑排列成圆圈。药片已编号 1, 2, \dots, N 按相邻顺序排列,以及片剂的重量 i is A_i。平板电脑 N 和平板电脑 1 也相邻。

高桥重复以下操作,直到只剩下一颗药片。

  • 选择圆圈上相邻的两个平板电脑,并将它们合并为一个。合并的成本等于两个所选药片的重量之和。合并创建的新平板电脑的权重也等于所选两个平板电脑的权重之和。新的平板电脑被放置在原来的两个平板电脑被移除的位置,并且与原来的两个平板电脑相对两侧的平板电脑相邻。这样,剩余的药片继续保持圆形结构。

找出所有操作中可能产生的最小总成本。

约束

  • 2 \leq N \leq 3000
  • 1 \leq A_i \leq 10^9
  • 所有输入均为整数

输入

N
A_1 A_2 \cdots A_N
  • 第一行包含一个整数 N 代表片剂数量。
  • 第二行包含整数 A_1, A_2, \dots, A_N 代表每片的重量,以空格分隔。

输出

在一行中打印最小总成本。


示例输入 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