环形石子合并（最大得分，每次合并相邻两堆，合并得分是两堆石子数量之和的平方）
1. 题目描述
有一个环形石子堆数组 stones[0..n-1]，其中 stones[i] 表示第 i 堆石子的数量。
现在你需要将这些石子堆合并成一堆，合并规则如下：
- 每次只能合并相邻的两堆石子。
- 合并的得分是这两堆石子数量之和的平方（即
(a + b)^2）。 - 合并后的新堆石子数量为两堆之和，并放在原来的位置参与后续合并。
- 由于是环形，首尾石子堆是相邻的。
问：将所有石子堆合并成一堆的最大得分是多少。
2. 问题分析
这是一个区间DP问题，但因为有“环形”条件，需要特殊处理。
线性版本（非环形）的合并规则为：
- 用
dp[l][r]表示合并区间[l, r]内的石子成一堆的最大得分。 - 区间长度从 2 到 n 枚举。
- 每次合并时，将区间分成左右两部分，分别先合并成两堆，再将这两堆合并，得分是这两堆石子总数的平方。
环形时，我们只需将原数组复制一份接在后面，在长度 2n 的数组上做线性DP，然后枚举所有长度为 n 的区间，求最大值即可。
3. 状态定义
设原数组长度为 n，构造新数组 a[0..2n-1]，其中
a[i] = stones[i % n] (i = 0..2n-1)
前缀和 prefix[i] 为 a[0..i] 的和，方便求区间和。
定义 dp[l][r] 表示将 a[l..r] 合并成一堆的最大得分。
4. 状态转移
对于区间 [l, r]：
-
如果
l == r，则只有一堆石子，不需要合并，得分 = 0。 -
否则，我们最后一次合并是将两堆（分别来自
[l, k]和[k+1, r]）合并成一堆。
这两堆的石子总数分别为：sum_left = prefix[k] - (l > 0 ? prefix[l-1] : 0) sum_right = prefix[r] - prefix[k]但更简单的做法是：我们不需要提前知道左右两堆的数量，因为最后一步的得分等于整个区间和的平方：
最后一步得分 = (sum(l, r)) ^ 2其中
sum(l, r)是a[l..r]的总和，可以用前缀和快速计算。那么：
dp[l][r] = max_{k = l .. r-1} { dp[l][k] + dp[k+1][r] } + (sum(l, r))^2含义是：先分别合并
[l,k]和[k+1,r]得到两堆，再合并这两堆得到最终一堆，最后一步得分是总和的平方。
5. 边界与初始化
- 长度为 1 的区间：
dp[l][l] = 0。 - 计算顺序：按区间长度
len从 2 到n（环形时我们在 2n 的数组上做到长度为 n 为止，但环形答案需要从每个起点取长度 n 的区间）。
6. 环形处理
在原数组后面复制一份得到长度 2n 的数组，做线性 DP 时，dp[l][r] 只在 r - l + 1 <= n 时计算（否则区间长度超过 n，不合法）。
最后答案：
ans = max_{i=0}^{n-1} dp[i][i + n - 1]
即枚举每个起点，合并连续 n 堆成一堆的最大得分。
7. 举例说明
假设原数组 stones = [1, 2, 3]，n=3。
扩展数组 a = [1, 2, 3, 1, 2, 3]。
前缀和 prefix = [1, 3, 6, 7, 9, 12]。
计算 dp[0][2]（合并前 3 堆）：
长度 2 区间：
dp[0][1]：合并 a[0],a[1] = 1,2
总和 = 3，最后得分 = 3^2 = 9。
dp[0][1] = 0 + 0 + 9 = 9。dp[1][2]：合并 a[1],a[2] = 2,3
总和 = 5，得分 = 25。
dp[1][2] = 0 + 0 + 25 = 25。
长度 3 区间 dp[0][2]：
总和 = 6，总和平方 = 36。
枚举 k：
- k=0：
dp[0][0]+dp[1][2] = 0 + 25 = 25，再加 36 → 61 - k=1：
dp[0][1]+dp[2][2] = 9 + 0 = 9，再加 36 → 45
取最大 61。
类似可计算其他起点。
最终答案取：
max(dp[0][2], dp[1][3], dp[2][4])
注意 dp[3][5] 是 a[3..5] 即 [1,2,3] 与 dp[0][2] 相同，因环形对称，不必重复。
计算后可得最大得分。
8. 时间复杂度与空间优化
- 时间复杂度 O(n^3)（枚举起点、长度、分割点），n 是原数组长度，在 2n 数组上计算长度 ≤ n 的区间，总 O((2n) * n^2) = O(n^3)。
- 空间复杂度 O(n^2)。
9. 关键点总结
- 环形问题转化为长度为 2n 的线性问题。
- 区间DP状态表示合并区间成一堆的最大得分。
- 转移时最后一步得分是整个区间和的平方，而不是左右两堆和的乘积（注意与“合并得分是两堆石子数量之和”不同，这里是平方，所以是固定的，与分界点无关，但分界点影响左右子区间的得分）。
- 最终答案是所有长度为 n 的区间的最大值。