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

15303105423

一、题目解读

牛客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作为答案。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     int n;
   
8.     cin >> n;
   
9.     vector<int> nums(n);
   
10.     for(int i = 0; i < n; ++i) {
    
11.         cin >> nums[i];
    
12.     }
    
13.    
    
14.     // 环形转线性：复制数组接在后面
    
15.     vector<int> arr(nums.begin(), nums.end());
    
16.     arr.insert(arr.end(), nums.begin(), nums.end());
    
17.    
    
18.     // dp[i][j]为合并i到j的最大能量
    
19.     vector<vector<int>> dp(2*n, vector<int>(2*n, 0));
    
20.    
    
21.     // 区间DP：枚举长度len和分割点k
    
22.     for(int len = 2; len <= n; ++len) {
    
23.         for(int i = 0; i + len - 1 < 2*n; ++i) {
    
24.             int j = i + len - 1;
    
25.             for(int k = i; k < j; ++k) {
    
26.                 // 状态转移方程：合并能量=子区间能量+首尾乘积
    
27.                 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + arr[i]*arr[k+1]*arr[j+1]);
    
28.             }
    
29.         }
    
30.     }
    
31.    
    
32.     // 找出所有n长度区间的最大值
    
33.     int res = 0;
    
34.     for(int i = 0; i < n; ++i) {
    
35.         res = max(res, dp[i][i+n-1]);
    
36.     }
    
37.     cout << res << endl;
    
38.    
    
39.     return 0;
    
40. }

复制代码

C++

五、总结

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

来源：信奥自学之路