6751. 克努斯划分 (Knuth Division)
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 给定一个包含 $n$ 个正整数的数组，你的任务是将其划分成 $n$ 个子数组，使得每个子数组中都仅包含单个元素。 在每次操作中，你可以选择任意一个长度大于 $1$ 的子数组，并将其拆分为两个更短的子数组。每次拆分操作的代价为所选子数组中所有元素的和。 如果采取最优策略，完成所有划分所需的最小总代价是多少？ ## 输入格式 第一行包含一个整数 $n$，表示数组的大小。 第二行包含 $n$ 个整数 $x\_1, x\_2, \dots, x\_n$，表示数组的初始内容。 ## 输出格式 输出一个整数，表示最小总代价。 ## 输入输出样例 ### 输入 #1 ``` 5 2 7 3 2 5 ``` ### 输出 #1 ``` 43 ``` ## 说明/提示 ### 数据规模与约定 * $1 \le n \le 5000$ * $1 \le x\_i \le 10^9$