AcWing 320. 能量项链
原题链接
中等
作者:
整天睡大觉
,
2024-04-24 13:14:05
,
所有人可见
,
阅读 1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210;
int n;
int g[N], f[N][N];
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> g[i], g[n + i] = g[i];
for(int len = 2; len <= n + 1; len ++){
for(int l = 1; l + len - 1 <= 2 * n; l ++){
int r = l + len - 1;
if(len == 2) f[l][r] = 0;
else{
for (int k = l + 1; k < r; ++ k)
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + g[l] * g[k] * g[r]);
}
}
}
int res = 0;
for(int l = 1; l <= n; l ++) res = max(res, f[l][l + n]);
cout << res;
}