Q. 多边形的三角划分

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$N$ 个顶点的凸多边形 [顶点顺序为1->N]，各顶点权值已知，要求划分成 $N-2$ 个三角形，使各三角形顶点权值乘积之和为最小。

当 $n=4$ ，各顶点的权值分别为 $10,5,7,6$ 时，所求最小值为 $10*5*6+5*6*7=510$ 。

第一行：一个整数 $n$ 。

第二行： $n$ 个整数,依次表示各顶点的权值。

一个整数表示最小的乘积之和。

4
10 5 7 6

$n \le 200$ ，所有输入数据均 $\le 1000$ ，所求得的最小值小于 $10^9$ 。