AcWing 320. 能量项链
原题链接
中等
O(n ^ 4) 118ms
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
int n;
int a[N];
int f[N][N]; // f[l][r]:[l, r] 合并释放能量的最大值
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i + n] = a[i];
int res = 0;
for (int start = 1; start <= n; start++) { // 枚举从哪个点开始合并
memset(f, 0, sizeof(f));
for (int len = 1; len <= n + 1; len++)
for (int l = start; l + len - 1 <= start + n - 1; l++) {
int r = l + len - 1;
for (int k = l; k <= r - 1; k++)
f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + a[l] * a[k + 1] * a[r + 1]);
}
res = max(res, f[start][start + n - 1]);
}
printf("%d", res);
return 0;
}
优化 O(n ^ 3) 18ms
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10;
int n;
int a[N];
int f[N][N]; // f[l][r]:[l, r] 合并释放能量的最大值
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i + n] = a[i];
for (int len = 1; len <= n; len++)
for (int l = 1; l + len - 1 <= 2 * n - 1; l++) {
int r = l + len - 1;
for (int k = l; k <= r - 1; k++)
f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + a[l] * a[k + 1] * a[r + 1]);
}
int res = 0;
for (int i = 1; i <= n; i++) res = max(res, f[i][i + n - 1]);
printf("%d", res);
return 0;
}