给定一个具有 $N$ 个顶点的凸多边形,将顶点从 $1$ 至 $N$ 标号,每个顶点的权值都是一个正整数。
将这个凸多边形划分成 $N-2$ 个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘都可得到一个权值乘积,试求所有三角形的顶点权值乘积之和至少为多少。
输入格式
第一行包含整数 $N$,表示顶点数量。
第二行包含 $N$ 个整数,依次为顶点 $1$ 至顶点 $N$ 的权值。
输出格式
输出仅一行,为所有三角形的顶点权值乘积之和的最小值。
数据范围
$N \le 50$,
数据保证所有顶点的权值都小于$10^9$
输入样例:
5
121 122 123 245 231
输出样例:
12214884
思路
这题本身不难,采用区间dp的思路,枚举三角形两个端点(l, r)和分段点k(l + 1, r - 1)然后推一下方程
f[l][r] = min(f[l][r], f[l][k] + f[k][r] + (LL)w[l] * w[r] * w[k])
但是w[l] * w[r] * w[k] 之后会爆longlong 需要写高精度就非常的蛋疼
然后我就用了 __int128处理大整数,但是 __int128 只能输入不能输出 需要重写输出(至少比高精度代码短) 用py写就很棒 py自带高精度(新语言就是好)
#include "bits/stdc++.h"
using namespace std;
typedef __int128 LL;
const int N = 55;
LL f[N][N];
int n;
int w[N];
ostream &operator << (ostream &out,LL x) {
if (!x) {
out << 0;
return out;
}
int stk[110],top = 0;
while (x) stk[++top] = x % 10,x /= 10;
for (int i = top;i >= 1;i--) out << stk[i];
return out;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int len = 3; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
f[l][r] = 1e126;
for (int k = l + 1; k < r; k++) {
f[l][r] = min(f[l][r], f[l][k] + f[k][r] + (LL)w[l] * w[r] * w[k]);
}
}
}
cout << f[1][n] << '\n';
return 0;
}