AcWing1069 - 凸多边形的划分
给定一个具有 N 个顶点的凸多边形,将顶点从 1 至 N 标号,每个顶点的权值都是一个正整数。
将这个凸多边形划分成 N−2 个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘都可得到一个权值乘积,试求所有三角形的顶点权值乘积之和至少为多少。
输入格式
第一行包含整数 N,表示顶点数量。
第二行包含 N 个整数,依次为顶点 1 至顶点 N 的权值。
输出格式
输出仅一行,为所有三角形的顶点权值乘积之和的最小值。
数据范围
N≤50, 数据保证所有顶点的权值都小于109
输入样例:
1
2
5
121 122 123 245 231
输出样例:
1
12214884
需要用int128或高精度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 55, M = 35, INF = 1e9;
int n;
int w[N];
LL f[N][N][M];
void add(LL a[], LL b[]) {
static LL c[M];
memset(c, 0, sizeof c);
for (LL i = 0, t = 0; i < M; i++) {
t += a[i] + b[i];
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}
void mul(LL a[], LL b) {
static LL c[M];
memset(c, 0, sizeof c);
for (LL i = 0, t = 0; i < M; i++) {
t += a[i] * b;
c[i] = t % 10;
t /= 10;
}
memcpy(a, c, sizeof c);
}
int cmp(LL a[], LL b[]) {
for (int i = M - 1; i >= 0; i--)
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
return 0;
}
void print(LL a[]) {
int k = M - 1;
while (k && !a[k]) k--;
while (k >= 0) cout << a[k--];
cout << endl;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
LL temp[M];
for (int len = 3; len <= n; len++)
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
f[l][r][M - 1] = 1;
for (int k = l + 1; k < r; k++) {
memset(temp, 0, sizeof temp);
temp[0] = w[l];
mul(temp, w[k]);
mul(temp, w[r]);
add(temp, f[l][k]);
add(temp, f[k][r]);
if (cmp(f[l][r], temp) > 0)
memcpy(f[l][r], temp, sizeof temp);
}
}
print(f[1][n]);
return 0;
}
This post is licensed under CC BY 4.0 by the author.