题解 CF1140D 【Minimum Triangulation】

SIGSEGV

2019-08-29 08:21:26

Solution

直接写了个区间 dp(这题有加强版:每个点的点权从输入中读取) 令 $dp_{i,j}$ 表示从点 $i$ 到点 $j$ 表示的区间内,三角划分的最小权值和为多少。 则显然 $dp_{i,j}=\min\{{dp_{i,k}+dp_{k,j}+ijk}\}$ (将 $i,j,k$ 三个点组成一个划分,再加上 $i$~$j$,$j$~$k$ 两段) ```cpp #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; } ```