凸多边形的划分

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1112 字

将N顶点凸多边形划分成N-2个三角形，求各三

一本通
例

正文

/*
原题：凸多边形的划分（三角剖分求三角形顶点权值乘积和的最小值）
题意：将 N 顶点凸多边形划分成 N-2 个三角形，求各三角形三顶点权值乘积之和最小。
思路：以边 (i,j) 为底、顶点 k 为第三点剖分：dp[i][j]=min{dp[i][k]+dp[k][j]+w[i]*w[j]*w[k]}。
复杂度：时间 O(N^3)，空间 O(N^2)
易错点：乘积与求和会超过 64 位，必须用 __int128；区间至少 3 点才可剖分，两点区间 dp 为 0。
*/
#include <bits/stdc++.h>
using namespace std;
void print128(__int128 x){
    if(x==0){cout<<0;return;}
    string s;
    while(x){
        s+=char('0'+(int)(x%10));
        x/=10;
    }
    reverse(s.begin(),s.end());
    cout<<s;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    vector<long long> w(N+1);
    for(int i=1;i<=N;i++) cin>>w[i];
    const __int128 INF=((__int128)1)<<120;
    vector<vector<__int128>> dp(N+1, vector<__int128>(N+1, INF));
    for(int i=1;i<N;i++) dp[i][i+1]=0;
    for(int len=3;len<=N;len++){
        for(int i=1;i+len-1<=N;i++){
            int j=i+len-1;
            for(int k=i+1;k<j;k++){
                __int128 cost=dp[i][k]+dp[k][j]+(__int128)w[i]*w[j]*w[k];
                if(cost<dp[i][j]) dp[i][j]=cost;
            }
        }
    }
    print128(dp[1][N]);
    cout<<"\n";
    return 0;
}

凸多边形的划分

正文

一本通·提高篇的其它内容