「一本通 5.1 例 3」凸多边形的划分 - Problem

Problem6953--「一本通 5.1 例 3」凸多边形的划分

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 256 MiB

给定一个具有 $N$ 个顶点的凸多边形，将顶点从 $1 \sim N$ 标号，每个顶点的权值都是一个正整数。
将这个凸多边形划分成 $N−2$ 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积。
试求所有三角形的顶点权值乘积之和至少为多少。

第一行包含整数 $N$，表示顶点数量。
第二行包含 $N$ 个整数，依次为顶点 $1$ 至顶点 $N$ 的权值。

输出仅一行，为所有三角形的顶点权值乘积之和的最小值。

$N≤50$,
数据保证所有顶点的权值都小于 $10^9$

5
121 122 123 245 231

12214884

相同题目：AcWing。

Submit