省流：区间 DP 水题
题目传送门
顾名思义，“项链”说明这个题是一个环，我们可以使用类似 这题 的操作，断环为链，就是在原数组后面拼一截：
for (int i = 1; i <= n; i++)a[i + n] = a[i];
然后正常区间 DP 即可。
设 \(dp_{l,r}\) 表示合并 \([l,r]\) 这个区间所产生的能量最大值。
转移：
\[dp_{l,r}=\max_{k=i}^{j-1} (dp_{i,k}+dp_{k,j}+a_ia_ja_k)
\]
套到代码里即可。
code
/*********************************************************** Author : dingziyang888* Website : https://www.luogu.com.cn/problem/* Created Time :* FileName :* Warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!* 1.MLE?* 2.array size enough?* 3.long long?* 4.overflow long long?* 5.multiple task cleaned?* 6.freopen?* 7.TLE?* *******************************************************/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iterator>
#include <map>
#include <unordered_map>
#include <queue>
#include <string>
#include <cstring>
#include <set>
#include <bitset>
#include <unordered_set>
#include <vector>
#include <deque>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <list>
#include <array>
#include <iterator>
#include <cmath>
#include <new>
#include <random>
#include <cfloat>
#include <cstdlib>
#include <climits>
#include <numeric>
#include <complex>
#include <ctime>
#include <chrono>
#include <thread>
#include <mutex>
#include <future>
#include <exception>
#include <stdexcept>
#include <cstdint>
#include <cassert>
#include <stack>
#include <cctype>
#define DEBUG
#define Ofile(s) freopen(s".in", "r", stdin), freopen (s".out", "w", stdout)
#define Cfile(s) fclose(stdin), fclose(stdout)
#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;using ll = long long;
using ull = unsigned long long;
using lb = long double;constexpr int mod = 998244353;
constexpr int maxn = 1005;int n, ans = -1;int a[maxn], dp[maxn][maxn];int main() {fast;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i], a[i + n] = a[i];for (int l = 2; l <= n + 1; l++)for (int i = 1; i + l - 1 <= n * 2; i++){int j = i + l - 1;for (int k = i + 1; k < i + l - 1; k++)dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[j] * a[k]);}for (int i = 1; i <= n; i++)ans = max(ans, dp[i][n + i]);cout << ans;return 0;
}