CF1140D Minimum Triangulation

给定一个有 $n$ 个顶点的正多边形，顶点按逆时针方向从 $1$ 到 $n$ 编号。对一个多边形的三角剖分是指将该多边形划分为若干个三角形，使得每个三角形的顶点都是原多边形的顶点，任意两个三角形的内部不相交，且所有三角形的面积之和等于原多边形的面积。一次三角剖分的权值定义为其包含的所有三角形权值之和，其中一个三角形的权值为其三个顶点编号的乘积。 请计算所有可能的三角剖分中，权值的最小值。

第一行包含一个整数 $n$（$3 \le n \le 500$），表示正多边形的顶点数。

输出一个整数，表示所有三角剖分中权值的最小值。

根据维基百科：多边形三角剖分是将一个多边形区域（简单多边形）$P$ 分解为若干个三角形，即找到一组两两内部不相交且并集为 $P$ 的三角形。 在第一个样例中，多边形本身就是一个三角形，无需再切分，因此答案为 $1 \cdot 2 \cdot 3 = 6$。 在第二个样例中，多边形是一个四边形，应将其划分为两个三角形。最优的方式是用对角线 $1-3$ 切分，因此答案为 $1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$。 由 ChatGPT 4.1 翻译