← 返回题目列表

AtCoder · kupc2012_10

J. 生鱼片

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

問題文

狐狸Shieru正在河里钓鱼。我得到了一条又长又黑的鱼,所以我决定当场把它切碎当生鱼片吃。

鱼有体长。 N 有厘米。奇怪的是,这条鱼身体不同部位的密度不同。 将鱼身从头开始分成1厘米的部分,并编号。 添加 1, 2, ..., N 时,指的是正文 第 i 部分的重量为 这是 w_i 。 鱼的 从第 i 起 部分至 j 让我们将其表示为 [i..j] 。 起初,Shieru拥有鱼的身体。 可以认为你只有一个 [0..N-1] 。 Shieru 剪掉了这个,最后 N 鱼体分成几块 我想要得到 [0..0], [1..1], ..., [N-1..N-1] 。

由于Shieru在野外并且没有切菜板,他决定使用以下杂技方法来切割鱼的身体:首先,取一块鱼的身体。这个 [i..j] 。这条鱼的身体必须至少有2厘米长。也就是说, 必须是 j-i ≥ 1 。然后将其扔到空中。然后,他手持一把日本刀,将漂浮的鱼切成两半。这时,Shieru可以利用他强大的运动神经在任何位置切割鱼,但他必须始终以1厘米的间隔切割。结果,原来的鱼身 [i..j] 在任何切割位置 通过 k (i ≤ k < j) , 它分为两部分:[i..k] 和 [k+1..j] 。 当使用这种杂技方法将鱼的身体切成两半时,原始身体的重量(=wi+wi+1+...+wj)。

Shieru 希望最小化将鱼的所有部分切成 1 厘米块的总成本。

入力形式

输入格式如下。

N\\
w1\ w2\ ...\ wN

N 是鱼的体长。w_i 是一条鱼 这是第 i 部分的重量。

出力形式

鱼 输出划分为 N 块的总成本的最小值。

制約

  • 2 ≤ N ≤ 4,000
  • 1 ≤ wi ≤ 1010
  • 所有输入值都是整数。

针对该问题的判断设置了一组3分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。

  • 1 ≤ N ≤ 100

入出力例

入力例 1

3
1 2 3

出力例 1

9

首先,将第二部分和第三部分之间的整条鱼切开。这花费 1+2+3 = 6。 接下来,在第一部分和第二部分之间进行切割。这花费1+2=3。这总共花费6+3=9,是最好的选择。

入力例 2

6
9876543210 9876543210 9876543210 9876543210 9876543210 9876543210

出力例 2

158024691360

入力例 3

10
127 131 137 139 149 151 157 163 167 173

出力例 3

5016

作者:楠本满
测试员:花田佑一郎