题目链接 AcWing 320. 能量项链
思路
1.先考虑线性做法(即不关注环)
2.采用 环拆链并复制一倍做法 (做法同 AcWing 1068. 环形石子合并)
C++代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> w[i];
w[i + n] = w[i];
}
for (int len = 3; len <= n + 1; len ++ ) //区间长度
for (int l = 1; l + len - 1 <= n * 2; l ++ ) //左端点
{
int r = l + len - 1; //右端点
for (int k = l + 1; k < r; k ++ )
f[l][r] = max(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
}
int res = 0;
for (int l = 1; l <= n; l ++ ) res = max(res, f[l][l + n]);
cout << res << endl;
return 0;
}