题目内容

小红拿到一个长度为 $n$ 的数组 ${a_1,a_2,...,a_n}$ ，下标从 $1$ 开始定义一次“合井”操作为：

选定任意的两个相邻的元素 $a_i$ 和 $a_{i+1}$ ，将它们合并成一个数，其余元素按照原有顺序从前到后依次拼接。这个数等于 $a_i$ 和 $a_{i+1}$ 的最大值，花费代价也是 $a_i$ 和 $a_{i+1}$ 的最大值，数组长度减少 $1$ 。

例如 $a=[1,2,3,4,5]$ ，小红可以选定 $a_2$ 和 $a_3$，合井成 $3$，数组变为 $[1,3,4,5]$，花费代价 $3$ 。

在执行上述的"合并"操作前，小红可以选择任意两个元素，将它们交换任意次(也可以不交换)。求解，执行恰好 $n-1$轮“合并“操作，使得将数组 $a$ 合并的只剩一个数，最少需要花费多少代价?

题解

题面描述

给定一个长度为 $n$ 的数组 $a=[a_1,a_2,\dots,a_n]$。可以任意交换数组中任意两个元素任意次（也可以不交换），使得可以自由调整顺序。然后定义一次“合井”操作：

• 选取相邻的两个数 $a_i$ 和 $a_{i+1}$，合并成一个数，该数等于 $\max\{a_i,a_{i+1}\}$，合并时花费代价也等于 $\max\{a_i,a_{i+1}\}$。
• 数组合并后顺序不变，但长度减少 $1$。

要求经过恰好 $n-1$ 次“合井”操作，使得最终数组只有一个数，问最少花费多少代价？