牛客AB52题解析：环形序列合并的动态规划解法

15303105423 · 发表于 2025-7-15 15:03:45

一、题目解读

牛客AB52题要求处理一个环形序列，通过合并相邻珠子释放能量，计算最大可释放能量值。题目核心在于环形结构的处理与动态规划的应用，需将环形问题转化为线性问题求解。

二、解题思路

采用动态规划（DP）解决该问题。首先，通过复制原数组形成长度为2n的线性序列，将环形结构转化为线性区间计算。随后，利用区间DP思想，定义dp[j]为合并区间[i,j]的最大能量，通过枚举分割点k优化状态转移。最终遍历所有n长度区间取最大值，得到答案。

三、解题步骤
1. 输入与初始化：读入序列n及元素，构建2n长度的arr数组。
2. 定义DP状态：dp[j]表示合并i到j珠子的最大能量。
3. 区间DP计算：
○ 枚举区间长度len=2~n，确保覆盖所有合法区间。
○ 枚举起点i，计算终点j，并遍历分割点k（i~j-1）。
○ 状态转移方程：dp[j] = max(dp[j], dp[k] + dp[k+1][j] + arr*arr[k+1]*arr[j+1])，即合并能量为子区间能量之和+当前区间首尾元素乘积。
4. 结果获取：遍历所有n长度区间dp[i+n-1]，取最大值res作为答案。
四、代码与注释

#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：枚举长度len和分割点k

for(int len = 2; len <= n; ++len) {

      for(int i = 0; i + len - 1 < 2*n; ++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] + 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;

}
复制代码

C++

五、总结
本解法关键在于环形结构到线性问题的转化，通过复制数组突破环形边界限制。区间DP通过枚举子区间分割点，有效解决组合优化问题。时间复杂度为O(n³)，空间复杂度O(n²)，适用于中小规模数据。掌握此类动态规划模型可高效解决类似环形序列优化问题。
来源：信奥自学之路