← 返回题目列表

Codeforces · 1140/D

D. 最小三角测量

中文机器翻译题面 查看原题

给定一个正多边形,其中 $$$n$$$ 顶点按逆时针顺序标记为从 $$$1$$$ 到 $$$n$$$。给定多边形的三角剖分是一组三角形,使得每个三角形的每个顶点都是初始多边形的顶点,不存在其交集具有非零面积的三角形对,并且所有三角形的总面积等于给定多边形的面积。三角剖分的权重是其组成的三角形的权重之和,其中三角形的权重表示为其顶点标签的乘积。

计算多边形的所有三角剖分中的最小权重。

输入

第一行包含单个整数 $$$n$$$ ($$$3 \le n \le 500$$$) — 正多边形中的顶点数。

输出

打印一个整数 — 给定多边形的所有三角剖分中的最小权重。

示例

输入 #1

3

输出 #1

6

输入 #2

4

输出 #2

18

注意

根据 Wiki:多边形三角剖分是将多边形区域(简单多边形)$$$P$$$ 分解为一组三角形,i。即,找到一组具有成对不相交内部的三角形,其并集为 $$$P$$$。

在第一个例子中,多边形是一个三角形,所以我们不需要进一步切割它,所以答案是 $$$1 \cdot 2 \cdot 3 = 6$$$。

在第二个示例中,多边形是矩形,因此应将其分为两个三角形。最好使用对角线 $$$1-3$$$ 进行切割,因此答案是 $$$1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$$$。