蓝桥杯算法提高-能量项链(区间DP）

解题思路:

对于每一对 (i, j)，我们考虑将第 k 颗珠子作为中间点，即先合并 i 到 k 的珠子，再合并 k+1 到 j 的珠子，最后合并这两部分。

长度为 1 的区间：单颗珠子无法释放能量，因此 dp[i][i] = 0。 

长度为 2 的区间：两颗珠子可以直接合并，计算它们释放的能量。 

更长的区间：通过将区间分成两部分，分别计算每部分的最大能量，再加上合并这两部分时释放的能量

枚举区间长度len（2 ~ n）

    枚举区间起点i（0 ~ 2n - len + 1）

        算出区间终点j = i+len-1

        枚举区间断点k（i <= k < j） 

            状态转移 注意事项:

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N = 1e2 + 10;
int a[N], dp[N][N]; 
int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i ++) {
		cin >> a[i];
		a[n + i] = a[i];
	}	
	// 动态规划填充 dp 数组
    for (int len = 2; len <= n; ++len) {
        for (int i = 0; i < 2*n - len + 1; ++i) {
            int j = (i + len - 1);
            for (int k = i; k < j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + a[i] * a[k+1] * a[j+1]);
            }
        }
    }
	int mx = 0;
	for(int i = 0; i < n; ++ i){
		mx = max(dp[i][i + n - 1],mx);
	}
	cout << mx;
	return 0;
}