題意：求將一個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;

}

 

總結

以上是生活随笔為你收集整理的题解 CF1140D 【Minimum Triangulation】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。