题目描述

你有一个凸的 $n$ 边形，其每个顶点都有一个整数值。给定一个整数数组 $values$ ，其中 $values[i]$ 是按  顺时针顺序 第 $i$ 个顶点的值。

假设将多边形 剖分  为 $n - 2$ 个三角形。对于每个三角形，该三角形的值是顶点标记的 乘积 ，三角剖分的分数是进行三角剖分后所有 $n - 2$ 个三角形的值之和。

返回 多边形进行三角剖分后可以得到的最低分 。

输入格式

第一行一个整数 $n$；

第二行 $n$ 个空格分开的整数表示 $value_i$。

输出格式

一行一个整数表示答案。

示例 1：

3
1 2 3

6

解释: 多边形已经三角化，唯一三角形的分数为 6。

示例 2：

4
3 7 4 5

144

解释: 有两种三角剖分，可能得分分别为：375 + 457 = 245，或 345 + 347 = 144。最低分数为 144。

示例 3：

6
1 3 1 4 1 5

13

解释: 最低分数三角剖分的得分情况为 113 + 114 + 115 + 111 = 13。

提示：

• $n == values.length$
• $3 <= n <= 50$
• $1 <= values[i] <= 100$

SOURCE

多边形三角剖分的最低得分