能量项链 - dp

解题思路:

处理环形结构：将环形项链"展开"成线性结构，通过复制一份数组来处理

        将长度为N的环形数组复制一份，形成长度为2N的线性数组

        这样，任何长度为N的连续子数组都可以表示原始环形结构中的一种可能情况

        例如，[1,2,3,4] → [1,2,3,4,1,2,3,4]，子数组[3,4,1,2]就是原环形数组的一种可能表示

定义状态：dp[i][j] 表示将区间[i,j]的珠子合并成一颗珠子所能释放的最大能量

    当合并两个子区间[i,k]和[k+1,j]时，释放的能量计算如下：

    a[i]：区间起始珠子的头标记（合并后新珠子的头标记）

    a[k+1]：分割点后一颗珠子的头标记（也是前一区间最后一颗珠子的尾标记）

    a[j+1]：区间结束后一颗珠子的头标记（也是当前区间最后一颗珠子的尾标记）

    状态转移：尝试所有可能的分割点，找出最优合并方式

结果：考虑所有可能的长度为N的连续区间，取最大值

参考代码:

#include <bits/stdc++.h>
#define INF 0x3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pr;
const int N = 1e5 + 10;
ll n;

int main() {
    int N;
    cin >> N;  // 读取珠子的数量
    
    // 读取每个珠子的头标记（1-indexed）
    vector<int> values(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> values[i];
    }
    
    // 为了处理环形结构，我们将数组复制一份
    // 这样可以处理任意连续的N个珠子，包括跨越原始首尾的情况
    vector<int> a(2 * N + 1);
    for (int i = 1; i <= N; i++) {
        a[i] = values[i];        // 原始数组
        a[i + N] = values[i];    // 复制的数组
    }
    
    // dp[i][j]表示将区间[i,j]合并成一颗珠子所能释放的最大能量
    vector<vector<int>> dp(2 * N + 1, vector<int>(2 * N + 1, 0));
    
    // 枚举区间长度，从2开始（至少需要两颗珠子才能合并）
    for (int len = 2; len <= N; len++) {
        // 枚举起始位置
        for (int i = 1; i <= 2 * N - len + 1; i++) {
            int j = i + len - 1;  // 计算终止位置
            
            // 枚举分割点k，尝试所有可能的合并方式
            for (int k = i; k < j; k++) {
                // 计算合并两个子区间后释放的能量
                // a[i]：左区间第一颗珠子的头标记
                // a[k+1]：右区间第一颗珠子的头标记（也是左区间最后一颗珠子的尾标记）
                // a[j+1]：右区间最后一颗珠子的尾标记（也是下一颗珠子的头标记）
                int energy = a[i] * a[k + 1] * a[j + 1];
                
                // 状态转移：尝试更新dp[i][j]
                // dp[i][k]：左区间[i,k]的最大能量
                // dp[k+1][j]：右区间[k+1,j]的最大能量
                // energy：合并这两个区间释放的能量
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + energy);
            }
        }
    }
    
    // 找出所有可能的起始位置中的最大值
    // 由于项链是环形的，我们需要考虑所有可能的"断开点"
    int maxEnergy = 0;
    for (int i = 1; i <= N; i++) {
        // dp[i][i+N-1]表示从位置i开始，连续N个珠子（即整个项链）的最大能量
        maxEnergy = max(maxEnergy, dp[i][i + N - 1]);
    }
    
    cout << maxEnergy << endl;
    
    return 0;
}