石子合并（环形版本） 题目描述 有 N 堆石子排成一个环形，第 i 堆石子有 a[ i ] 颗（下标从 1 开始）。现要将石子有次序地合并成一堆，规定每次只能合并相邻的两堆，合并的代价为这两堆石子的数量之和。问合并成一堆的总代价最小是多少？ 输入：一个环形数组 a[ 1..N ]（N ≥ 1）。 输出：一个整数，表示最小总代价。 示例 输入：a = [ 4, 4, 5, 9 ]（环形排列） 输出：43 解释：一种最优合并顺序为 ((4⊕4)⊕(5⊕9)) → 总代价 = 8 + 14 + 22 = 43（⊕表示合并操作，代价为两堆之和）。 解题过程循序渐进讲解 1. 问题分析 线性版（非环形）：N 堆石子排成一行，每次合并相邻两堆，求最小代价。经典的区间 DP 问题。 环形版：N 堆排成环，即 a[ N] 与 a[ 1 ] 也相邻。我们可以在任意位置“断开”环，转化为长度为 N 的线性问题，但需要枚举所有断点。 目标：找到一种合并顺序，使得总代价最小。总代价 = 每次合并代价之和。 2. 线性版石子合并的回顾 定义 dp[ i][ j] 表示合并区间 [ i, j ] 内的所有石子成一堆的最小代价（i ≤ j）。 状态转移：考虑最后一次合并，一定是由 [ i, k] 和 [ k+1, j] 两堆合并而成（i ≤ k < j）。合并这两堆的代价是 sum(i, j)（区间和）。 转移方程： dp[ i][ j] = min{ dp[ i][ k] + dp[ k+1][ j ] + sum(i,j) }，其中 k 从 i 到 j-1。 初始化：dp[ i][ i ] = 0（一堆不需要合并）。 最终答案：dp[ 1][ N ]（假设下标从 1 开始）。 计算顺序：按区间长度从小到大计算。 3. 环形版的转化思路 环形数组 a[ 1..N ] 可以看作在任意位置切开形成的 N 种不同的线性排列。例如，从位置 p 切开得到线性序列： a[ p], a[ p+1], ..., a[ N], a[ 1], ..., a[ p-1 ]（长度为 N）。 我们需要对每种切法（p=1..N）计算线性版的最小代价，然后取最小值。 暴力枚举断点的时间复杂度是 O(N) × O(N³) = O(N⁴)，太高。优化方法：将原数组复制一倍，构造长度 2N 的线性数组 b，其中 b[ i] = a[ i mod N]（1-based，若 i%N==0 则取 a[ N ]）。 具体：b[ 1..2N] = a[ 1], a[ 2], ..., a[ N], a[ 1], a[ 2], ..., a[ N ]。 则原环上任意一段长度为 N 的连续子序列都对应 b 中某个长度为 N 的区间。合并这个长度为 N 的区间的最小代价可以用线性 DP 计算。我们需要计算所有起点 s=1..N 对应的区间 [ s, s+N-1 ] 的 dp 值，取最小值。 4. 环形版的具体 DP 设计 设 b[ 1..2N ] 为复制后的数组。 定义 dp[ i][ j] 表示合并 b 的区间 [ i, j] 成一堆的最小代价（1 ≤ i ≤ j < i+N ≤ 2N）。 转移方程同线性版： dp[ i][ j] = min{ dp[ i][ k] + dp[ k+1][ j] + sum(i,j) }，i ≤ k < j。 其中 sum(i,j) 是 b[ i..j ] 的和，可用前缀和快速计算。 初始化：dp[ i][ i ] = 0。 计算顺序：区间长度 len 从 2 到 N（因为最终我们只关心长度 N 的区间）。 答案：min{ dp[ s][ s+N-1 ] }，s=1..N。 5. 前缀和优化 令 prefix[ i] = b[ 1] + b[ 2] + ... + b[ i]，则 sum(i,j) = prefix[ j] - prefix[ i-1 ]。 在代码中，我们通常用 prefix[ 0]=0，prefix[ i]=prefix[ i-1]+b[ i ]。 6. 逐步计算示例 以 a = [ 4,4,5,9 ] 为例，N=4。 构造 b = [ 4,4,5,9,4,4,5,9 ]。 前缀和 prefix（0-based 方便）： i:0 1 2 3 4 5 6 7 8 b: 4 4 5 9 4 4 5 9 prefix:0 4 8 13 22 26 30 35 44 我们计算 dp[ i][ j ] 表（1-based 索引），区间长度 len 从 2 到 4。 下面只展示关键计算过程，最终得到各起点 s 的 dp[ s][ s+3 ]： s=1: 区间 [ 1,4 ] 对应原环的 4,4,5,9。 计算得 dp[ 1][ 4 ] = 43（后面验证）。 s=2: 区间 [ 2,5] 对应 4,5,9,4 → dp[ 2][ 5 ] = 41。 s=3: 区间 [ 3,6] 对应 5,9,4,4 → dp[ 3][ 6 ] = 41。 s=4: 区间 [ 4,7] 对应 9,4,4,5 → dp[ 4][ 7 ] = 43。 取最小值 41？等等，示例说答案是 43，我们检查。 实际上，示例输出 43 对应的是原题给出的一个最优合并方式，但可能存在更小的。我们需要准确计算。 手动验证 s=1 时合并 4,4,5,9： 方案1: ((4⊕4)⊕(5⊕9)) → 合并 4,4 代价 8，得到 8,5,9；合并 5,9 代价 14，得到 8,14；合并 8,14 代价 22，总 8+14+22=44？不对，应该是 8+14+22=44，但示例说是 43。 方案2: (4⊕(4⊕(5⊕9))) → 合并 5,9 代价 14，得 4,4,14；合并 4,4 代价 8，得 8,14；合并 8,14 代价 22，总 14+8+22=44。 方案3: (((4⊕4)⊕5)⊕9) → 合并 4,4=8，得 8,5,9；合并 8,5=13，得 13,9；合并 13,9=22，总 8+13+22=43。 所以最小代价是 43。 计算 dp[ 1][ 4 ]： len=2: dp[ 1][ 2]=8, dp[ 2][ 3]=9, dp[ 3][ 4]=14, dp[ 4][ 5]=13, dp[ 5][ 6]=8, dp[ 6][ 7]=9, dp[ 7][ 8 ]=14。 len=3: dp[ 1][ 3]=min(dp[ 1][ 2]+dp[ 3][ 3]+sum(1,3), dp[ 1][ 1]+dp[ 2][ 3 ]+sum(1,3)) = min(8+0+13, 0+9+13)=min(21,22)=21。 dp[ 2][ 4]=min(dp[ 2][ 3]+dp[ 4][ 4]+sum(2,4), dp[ 2][ 2]+dp[ 3][ 4 ]+sum(2,4)) = min(9+0+18, 0+14+18)=min(27,32)=27。 dp[ 3][ 5]=min(dp[ 3][ 4]+dp[ 5][ 5]+sum(3,5), dp[ 3][ 3]+dp[ 4][ 5 ]+sum(3,5)) = min(14+0+18, 0+13+18)=min(32,31)=31。 dp[ 4][ 6 ]=min(13+0+17, 0+8+17)=min(30,25)=25。 dp[ 5][ 7 ]=min(8+0+18, 0+9+18)=min(26,27)=26。 dp[ 6][ 8 ]=min(9+0+18, 0+14+18)=min(27,32)=27。 len=4: dp[ 1][ 4]=min( dp[ 1][ 1]+dp[ 2][ 4]+sum(1,4), dp[ 1][ 2]+dp[ 3][ 4]+sum(1,4), dp[ 1][ 3]+dp[ 4][ 4 ]+sum(1,4) ) = min(0+27+22, 8+14+22, 21+0+22) = min(49, 44, 43) = 43。 所以 dp[ 1][ 4 ]=43。 类似计算其他起点，最后取 min{43, 41, 41, 43}=41。 所以最优解是 41，不是 43。这说明原示例给出的 43 并非最优。 实际上，当 a=[ 4,4,5,9 ] 时，环形合并的最小代价确实是 41。验证如下： 取序列 4,5,9,4（起点 s=2）： 合并 5,9=14 → 4,14,4；合并 4,4=8 → 8,14；合并 8,14=22；总 14+8+22=44？不对，这样是 44。 取序列 5,9,4,4（起点 s=3）： 合并 4,4=8 → 5,9,8；合并 5,9=14 → 14,8；合并 14,8=22；总 8+14+22=44。 计算 s=2 的 dp[ 2][ 5 ]： dp[ 2][ 5] 对应 b[ 2..5 ]=4,5,9,4。 len=2: dp[ 2][ 3]=9, dp[ 3][ 4]=14, dp[ 4][ 5 ]=13。 len=3: dp[ 2][ 4]=min(9+0+18, 0+14+18)=27, dp[ 3][ 5 ]=min(14+0+18,0+13+18)=31。 len=4: dp[ 2][ 5 ]=min(0+31+22, 9+13+22, 27+0+22) = min(53, 44, 49) = 44。 所以 dp[ 2][ 5]=44，不是 41。我之前的 41 计算有误。重新计算 s=3 的 dp[ 3][ 6 ]： b[ 3..6 ]=5,9,4,4。 len=2: dp[ 3][ 4]=14, dp[ 4][ 5]=13, dp[ 5][ 6 ]=8。 len=3: dp[ 3][ 5]=min(14+0+18, 0+13+18)=31, dp[ 4][ 6 ]=min(13+0+17, 0+8+17)=25。 len=4: dp[ 3][ 6 ]=min(0+25+22, 14+8+22, 31+0+22) = min(47, 44, 53) = 44。 所以四个起点的 dp 值都是 43 或 44。最小值是 43。 原示例输出 43 是对的，且确实是最小值。 7. 算法步骤总结 读入环形数组 a[ 1..N ]。 构造长度 2N 的数组 b，其中 b[ 1..N]=a[ 1..N], b[ N+1..2N]=a[ 1..N ]。 计算前缀和 prefix[ 0..2N]，prefix[ 0]=0, prefix[ i]=prefix[ i-1]+b[ i ]。 初始化 dp 数组大小为 (2N+1)×(2N+1)，dp[ i][ i ]=0。 枚举区间长度 len=2 到 N： 枚举起点 i=1 到 2N-len+1： j=i+len-1。 dp[ i][ j ]=∞。 枚举分割点 k=i 到 j-1： cost = dp[ i][ k] + dp[ k+1][ j] + (prefix[ j]-prefix[ i-1 ])。 dp[ i][ j] = min(dp[ i][ j ], cost)。 答案 ans = min{ dp[ s][ s+N-1 ] }，s=1..N。 输出 ans。 8. 复杂度分析 时间复杂度：O(N³)，因为三层循环：长度 O(N)，起点 O(N)，分割点 O(N)，总共 O(N³)。当 N≤350 时可行。 空间复杂度：O(N²)，存储 dp 表。 9. 核心思想 环形问题通过复制数组转化为线性问题，从而可以用区间 DP 统一求解所有起点的合并代价，避免枚举断点带来的额外复杂度因子。