能量项链，洛谷

本文主要是介绍能量项链，洛谷，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解释：

 环形dp问题还是考虑将环拉直，可以参考我上一篇文章：环形石子合并

[2 3 5 10 2] 3 5 10 将环拉直，[]内是一个有效的区间，可以模拟吸收珠子的过程，

        如[2 3 5] <=>(2,3)(3,5)    2是头，3是中间，5是尾

len >= 3：因为最后[2 10 2]是最小的可以合并的有效区间

len <= n + 1因为[2 3 5 10 2] 3 5 10 是一个满足题意的区间

k枚举的是可以吸收掉的珠子的位置，L + 1 <= k < R

若有帮助理解，点个赞吧

#include <iostream>
#include <algorithm>using namespace std;
using LL = long long;const int N = 2e2 + 9;int n;
LL w[N],s[N];
LL f[N][N];void solve()
{cin >> n;for (int i = 1;i <= n;i ++){cin >> w[i];w[i + n] = w[i];}	for (int i = 1;i <= 2 * n;i ++) s[i] = s[i - 1] + w[i];for (int len = 3;len <= n + 1;len ++)for (int i = 1;i + len - 1 <= 2 * n;i ++){int j = i + len - 1;for (int k = i + 1;k < j;k ++){f[i][j] = max(f[i][j],f[i][k] + f[k][j] + w[i] * w[k] * w[j]);}}LL ans = 0;for (int i = 1;i <= n;i ++)ans = max(ans,f[i][i + n]);cout << ans << endl;
}

这篇关于能量项链，洛谷的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---