Knuth Division

题目描述

给定一个包含 $n$ 个数的数组，你的任务是将其划分为 $n$ 个子数组，每个子数组恰好包含一个元素。 在每一步，你可以选择任意一个子数组并将其拆分为两个子数组。该步的代价是所选子数组中元素之和。 如果你采用最优策略，最小的总代价是多少？

输入格式

第一行输入包含一个整数 $n$：数组的大小。数组元素按编号 $1,2,\dots,n$。 第二行包含 $n$ 个整数 $x_1,x_2,\dots,x_n$：数组的元素。

输出格式

输出一个整数：最小的总代价。

5
2 7 3 2 5

43

提示

$1 \le n \le 5000$ $1 \le x_i \le 10^9$

标签: CSES2088|先进技术

来源

CSES2088|先进技术