环形石子合并的最大得分问题（进阶版：带权值） 题目描述 在一条环形石子链上有 \( n \) 堆石子排成一个环，第 \( i \) 堆石子的数量为 \( a[ i ] \)（下标从 0 到 \( n-1 \)）。 每次可以合并相邻的两堆石子，合并的得分定义为： 合并后的新石子堆的石子数量 乘以一个权重 \( w \)（这里权重 \( w \) 是合并时这两堆石子中左边那堆的原始编号对应的固定权重值，即 \( w[ 左堆原编号 ] \)）。 合并后得到的新石子堆会占据原来的位置，并且继承左边那堆的原始编号（用于后续合并的权重计算）。 我们需要将所有石子合并为一堆，求最大总得分。 更形式化地说 ： 初始有 \( n \) 堆石子围成一个环。 每堆石子有两个属性：数量 \( a[ i] \) 和固定权重 \( w[ i ] \)。 合并操作：选择相邻两堆 \( i \) 和 \( i+1 \)（在环形意义上相邻），设左边那堆的原编号是 \( p \)，右边那堆的原编号是 \( q \)。 合并得分为：\( (a[ p] + a[ q]) \times w[ p ] \)。 合并后新堆的数量为 \( a[ p] + a[ q] \)， 新堆的原编号继承为 \( p \) （即权重仍是 \( w[ p] \)，不会变成 \( w[ q ] \)）。 问将所有堆合并为一堆的最大总得分。 注意：这里的“原编号”是初始时每堆的编号，不随合并而改变（除了继承左边那堆的），因此权重是固定的。 这增加了问题的难度，因为合并顺序会影响后续合并的权重。 解题思路 这是一个环形区间 DP 问题，但和经典“环形石子合并”不同之处在于： 经典问题中得分是两堆石子数量之和，没有权重。 这里得分是两堆石子数量之和乘以 左边堆的固定权重 ，这意味着在合并区间时，我们需要知道最终合并出来的这个“大堆”的原编号是哪个（即它继承的是初始的哪一堆的权重）。 1. 化环为链 经典技巧：将环复制一倍，变成长度为 \( 2n \) 的链 \( a[ 0..2n-1] \)，\( w[ 0..2n-1 ] \) 同样复制。 我们只需要枚举链中一个长度为 \( n \) 的区间作为起点，在这个区间内进行线性 DP，最后取最大值即可。 2. 状态定义 设 \( dp[ l][ r ] \) 表示将环形中（对应到链的某段）从第 \( l \) 堆到第 \( r \) 堆的所有堆合并成一堆时，所能获得的最大得分。 但这里有一个问题：合并后这一堆的“原编号”是哪个？因为后续与它相邻堆合并时，它的权重会影响得分，所以必须记录。 因此状态必须增加一维，记录这个区间最终合并出来的那一堆的“原编号”。 设 \( dp[ l][ r][ k] \) 表示将区间 \([ l, r]\) 合并成一堆，且这一堆继承的原编号是初始的第 \( k \) 堆（即权重为 \( w[ k ] \)）时，能得到的最大得分。 显然 \( k \) 必须是区间 \([ l, r ]\) 中某个堆的原始编号，并且是最终存活下来的“代表编号”。 实际上，在合并过程中，区间 \([ l, r]\) 最后剩下的那个“代表编号”一定是这个区间最初 最左边 的那个编号 \( l \)（因为在环形 DP 中，当我们从小区间合并到大区间时，总是让左边那堆的编号存活下来，这是由合并规则决定的：合并时总是保留左边堆的编号）。 因此，我们不必记录第三维 \( k \)，而是约定： 对于区间 \([ l, r]\)，最后合并出来的那一堆的固定编号就是 \( l \) （即权重为 \( w[ l ] \)）。 这样，状态可以简化为： \( dp[ l][ r] \) 表示将区间 \([ l, r]\) 内的所有堆合并成一堆，并且最终这一堆的编号是 \( l \)（权重为 \( w[ l ] \)）时，能获得的最大得分。 3. 状态转移 考虑区间 \([ l, r ]\) 的最后一次合并： 最后一次合并一定是将区间 \([ l, m]\) 合并成的一堆（编号为 \( l \)）与区间 \([ m+1, r ]\) 合并成的一堆（编号为 \( m+1 \)）进行合并。 合并得分为： \[ (a\_sum[ l][ m] + a\_sum[ m+1][ r]) \times w[ l ] \] 其中 \( a\_sum[ l][ m] \) 是区间 \([ l, m]\) 的总石子数，\( a\_sum[ m+1][ r] \) 是区间 \([ m+1, r ]\) 的总石子数。 合并后新堆编号为 \( l \)（左边堆的编号），权重是 \( w[ l ] \)。 那么： \[ dp[ l][ r] = \max\_{m = l}^{r-1} \left\{ dp[ l][ m] + dp[ m+1][ r] + (a\_sum[ l][ m] + a\_sum[ m+1][ r]) \times w[ l ] \right\} \] 这里 \( dp[ l][ m] \) 是将 \([ l, m]\) 合并成一堆（编号为 \( l \)）的最大得分，\( dp[ m+1][ r] \) 是将 \([ m+1, r ]\) 合并成一堆（编号为 \( m+1 \)）的最大得分。 4. 初始化 长度为 1 的区间：\( dp[ i][ i ] = 0 \)，因为只有一堆，不需要合并，得分为 0。 5. 前缀和优化 为了快速计算区间石子总数，预处理前缀和数组 \( sum[ i] \) 表示 \( a[ 0] + a[ 1] + \dots + a[ i ] \)（在链上）。 则 \( a\_sum[ l][ r] = sum[ r] - sum[ l-1 ] \)（注意处理边界）。 6. 环形处理 由于是环形，我们只需要在链 \( 0..2n-1 \) 上进行 DP，但只计算长度从 1 到 \( n \) 的区间，且起点 \( l \) 从 0 到 \( n-1 \) 枚举，取 \( dp[ l][ l+n-1 ] \) 的最大值作为答案。 7. 复杂度 状态数 \( O(n^2) \)（链长度 \( 2n \) 时是 \( O((2n)^2) = O(n^2) \)），转移枚举分割点 \( O(n) \)，总复杂度 \( O(n^3) \)。 在 \( n \le 200 \) 时可行。 示例 设 \( n = 3 \)，石子数 \( a = [ 1, 2, 3] \)，权重 \( w = [ 4, 5, 6 ] \)。 环形复制后： \( a' = [ 1, 2, 3, 1, 2, 3 ] \) \( w' = [ 4, 5, 6, 4, 5, 6 ] \) 我们以起点 0 为例（即区间 [ 0, 2 ] 对应原环）： 长度 1：dp[ 0][ 0]=0, dp[ 1][ 1]=0, dp[ 2][ 2 ]=0 长度 2： dp[ 0][ 1] = dp[ 0][ 0] + dp[ 1][ 1] + (a[ 0]+a[ 1]) w[ 0] = 0 + 0 + (1+2) 4 = 12 dp[ 1][ 2] = 0 + 0 + (2+3)* 5 = 25 长度 3： dp[ 0][ 2 ] = max{ (1) 分割点 0：dp[ 0][ 0]+dp[ 1][ 2]+(a[ 0]+(a[ 1]+a[ 2])) w[ 0] = 0+25+(1+5) 4 = 0+25+24=49 (2) 分割点 1：dp[ 0][ 1]+dp[ 2][ 2]+((a[ 0]+a[ 1])+a[ 2]) w[ 0] = 12+0+(3+3) 4 = 12+24=36 } = 49 所以从原环的 0 号开始合并，最大得分 49。 还需要枚举起点 1 和 2，取最大。 总结 本题是环形石子合并的进阶版，关键点在于理解合并时“固定权重”属于左边堆，并因此在状态设计和转移中保持一致——最终区间的代表编号是最左边那个。 通过化环为链和区间 DP 可求解。