题解 CF1140D 【Minimum Triangulation】

题意：求将一个n边形分解成(n-2)个三边形花费的最小精力，其中花费的精力是所有三角形的三顶点编号乘积的和(其中编号是按照顶点的顺时针顺序编写的)

考虑1,x,y连了一个三角形，x,y,z连了一个三角形。权值为xy+xyz。

换一种连接方法，1,x,z和1,y,z。权值为xz+yz 考虑x,y≥2时，x+y≤xy，所以后者剖分方法要优于前者剖分方法。

所以答案是(n³-n)÷3－2

AC代码：

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n;

    cin>>n;

    cout<<(n*n*n-n)/3-2;

    return 0;

}

巴特西