牛客AB52能量项链问题：环形区间DP的完美应用

4天前牛客题解64

一、问题背景与理解

能量项链问题描述了一个环形排列的珠子序列，每个珠子有头尾标记。通过特定的聚合操作，相邻珠子可以合并并释放能量。我们的目标是找到使总能量最大的聚合顺序。这个问题本质上是一个环形区间动态规划问题，与矩阵连乘问题类似但更具挑战性。

二、算法核心思想

环形问题线性化：将原数组复制一份接在后面，转化为线性问题处理
区间DP定义：dp[i][j]表示合并第i到第j颗珠子能获得的最大能量
状态转移方程：dp[i][j] = max(dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1])，其中k为分割点
边界条件：当区间长度为1时(dp[i][i])，能量为0

三、实现详解

输入处理：读取珠子数量n和头标记数组
环形转线性：将原数组复制一份接在后面，形成2n长度的数组
DP数组初始化：创建2n×2n的二维数组，初始值设为0
区间DP计算：

外层循环枚举区间长度(从2到n)
中层循环枚举区间起点
内层循环枚举分割点k，计算所有可能分割方式的最大值

结果提取：在转换后的线性数组中，找出所有长度为n的区间中的最大值

四、代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    // 环形问题转化为线性问题：将数组复制一份接在后面
    vector<int> arr(nums.begin(), nums.end());
    arr.insert(arr.end(), nums.begin(), nums.end());
    
    // dp[i][j]表示合并i到j颗珠子的最大能量
    vector<vector<int>> dp(2*n, vector<int>(2*n, 0));
    
    // 区间DP：枚举区间长度
    for(int len = 2; len <= n; ++len) {
        // 枚举区间起点
        for(int i = 0; i + len - 1 < 2*n; ++i) {
            int j = i + len - 1; // 区间终点
            // 枚举分割点k
            for(int k = i; k < j; ++k) {
                // 状态转移方程：dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1])
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1]);
            }
        }
    }
    
    // 找出所有长度为n的区间中的最大值
    int res = 0;
    for(int i = 0; i < n; ++i) {
        res = max(res, dp[i][i+n-1]);
    }
    cout << res << endl;
    
    return 0;
}