题解 CF1140D 【Minimum Triangulation】
SIGSEGV
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$ 两段)
```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;
}
```