题解 CF1140D 【Minimum Triangulation】

2019-08-29 08:21:26


直接写了个区间dp(这题有加强版:每个点的点权从输入中读取)

令 $dp_{i,j}$ 表示从点 $i$ 到点 $j$ 表示的区间内,三角划分的最小权值和为多少。

则显然 $dp_{i,j}=\min\{{dp_{i,k}+dp_{k,j}+ijk}\}$ (将 $i,j,k$ 三个点组成一个划分,再加上 $i$ ~ $j$ , $j$ ~ $k$ 两段)

#include <bits/stdc++.h>
using namespace std;
int n;
long long dp[505][505];
int main ()
{
    scanf("%d",&n);
    memset(dp,-1,sizeof(dp));
    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++)
                if (dp[i][j] == -1 || dp[i][j] > dp[i][k] + dp[k][j] 
                    + i * j * k) 
                    dp[i][j] = dp[i][k] + dp[k][j] + i * j * k;
        }
    printf("%I64d",dp[1][n]);
    return 0;
}