题目
题目描述
给定一个具有N个顶点的凸多边形，将顶点从1至N标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成N-2个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。
输入描述
输入第一行为顶点数N
第二行依次为顶点1至顶点N的权值。
输出描述
输出仅一行，为这些三角形顶点的权值乘积和的最小值。
示例1
输入
5
121 122 123 245 231
输出
12214884
备注
对于 \(100 \%\) 的数据，有 \(N \leq 50\) ，每个点权值小于 \(10^9\) 。
题解
知识点：区间dp。
第一眼是带环的区间dp，但仔细一想是不需要的。
设 \(dp[i][j]\) 为区间 \([i,j]\) 的点构成的多边形的最大权值。转移方程为：
\[dp[i][j] = \max(dp[i][k]+dp[k][j] + a[i]\cdot a[j] \cdot a[k]) \]表示为 \([i,k],[k,j]\) 与 \(i,j,k\) 构成的三角能合并成 \([i,j]\) 构成的多边形。
注意到如果答案是由 \([i,n,1,k],[k,i-1]\) 前者是跨越 \(n,1\) 的区间合成，那么一定被 \([1,k],[k,n]\) 这种情况包括了，所以不需要考虑环状结构。
注意会超 long long ，用 __int128 。
时间复杂度 \(O(n^3)\)
空间复杂度 \(O(n^2)\)
代码
#include <bits/stdc++.h>
using namespace std;
__int128 a[57], dp[57][57];
template<class T>
inline void read(T &val) {
T x = 0, f = 1;char c = getchar();
while (c < '0' || c>'9') { if (c == '-') f = -1;c = getchar(); }///整数符号
while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48);c = getchar(); }///挪位加数
val = x * f;
}
template<class T>
inline void write(T x) {
if (x < 0) { putchar('-');x = -x; }
if (x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
read(n);
for (int i = 1;i <= n;i++) read(a[i]);///不需要化环为链，因为只需要1和n连就已经全包括了
memset(dp, 0x3f, sizeof(dp));
for (int i = 1;i <= n;i++)
dp[i][i] = dp[i][i + 1] = 0;
for (int l = 3;l <= n;l++) {
for (int i = 1;i <= n - l + 1;i++) {
int j = i + l - 1;
for (int k = i;k < j;k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + (__int128)a[i] * a[k] * a[j]);
}
}
write(dp[1][n]);
puts("");
return 0;
}