题意

给定一个具有 $N$ 个顶点的凸多边形，将顶点从 $1$ 至 $N$ 标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。

思路

首先随便搞一个多边形：

然后给它顺时针每个顶点表上序号：

然后枚举$i,j$，要求：$i+1<j$，然后给$i,j$连一条线，分割出来另一个多边形：多边形23456

然后在$i,j$范围内枚举$k$，使得多边形23456又可以分割。

分割成如下图：

设$f[i][j]$表示把$i,j$的多边形切割成三角形后的权值乘积之和的最小值。 可得：
$$f[i][j]=min{f[i][k]+f[k][j]+a[i]a[j]a[k]}(0<i<j<k\leq n)$$
初始化：
$$f[i][j]=inf(0<i\leq n,0<j\leq n)$$ $$f[i][i+1]=0(0<i<n)$$ 时间复杂度：$O(n^3)$ 输出结果：$f[1][n]$ 当然，这道题范围特别大：对于 $100\%$ 的数据，有 $N\le 50$，每个点权值小于 $10^9$。三个数相乘最高可达$10^{27}$，所以需要使用高精度。这里使用了C++大数类，转自代号4101