合并石子获得最大得分问题（带权值版本）
题目描述
假设有 n 堆石子排成一行，每堆石子有一个重量值 w[i]（正整数），以及一个附加权值 v[i]（可正可负）。你可以进行 n-1 次合并操作，每次合并选择相邻的两堆石子 i 和 i+1，将它们合并为一堆新的石子，新石子的重量为两堆石子重量之和，而本次合并的得分为：
(w[i] + w[i+1]) * (v[i] + v[i+1])
合并后，新石子的重量为 w[i] + w[i+1]，附加权值为 v[i] + v[i+1]。合并后原两堆石子消失，新石子占据原两堆的位置（即序列长度减 1）。目标是选择合并的顺序，使得总得分最大。
示例
n = 3
重量 w = [2, 3, 4]
权值 v = [1, -1, 2]
一种合并顺序：
- 先合并前两堆：得分 = (2+3)(1+(-1)) = 50 = 0，新石子重量=5，权值=0，序列变为 [5,4] 和 [0,2]。
- 合并剩下两堆：得分 = (5+4)(0+2) = 92 = 18，总得分 = 0+18 = 18。
另一种合并顺序可能得到不同总分，需要找出最大值。
解题过程
步骤 1：理解问题结构
这是一个区间动态规划问题，因为：
- 每次合并相邻两堆，类似石子合并经典问题。
- 合并后的新石子有新的重量和权值，会影响后续合并的得分。
- 需要按不同顺序尝试，找到最大总分。
设：
w[i]为第 i 堆初始重量。v[i]为第 i 堆初始权值。
合并区间 [i, j] 时，最终合并成一堆，其总重量是固定的，为 sum(w[i..j])，与合并顺序无关。
但总权值也是固定的，为 sum(v[i..j])，也与合并顺序无关。
为什么？因为每次合并只是把两堆的重量和权值分别相加，加法满足结合律，所以最终的总重量和总权值不变。
但得分与合并顺序有关，因为得分计算式为 (w_left + w_right) * (v_left + v_right)，其中 w_left 和 v_left 是左区间合并后的总重量和总权值，w_right 和 v_right 是右区间合并后的总重量和总权值。
不同的合并顺序会导致不同的中间合并时的左右重量和权值组合，从而影响得分。
步骤 2：定义状态
设：
dp[i][j]表示将区间 [i, j] 的石子合并成一堆时，能获得的最大总得分（i ≤ j）。sumW[i][j]表示区间 [i, j] 的石子总重量，可前缀和快速计算。sumV[i][j]表示区间 [i, j] 的石子总权值，同样可前缀和计算。
注意：区间 [i, j] 合并成一堆后，它的总重量 = sumW[i][j]，总权值 = sumV[i][j]，这是确定的，与怎么合并无关。
步骤 3：状态转移
考虑最后一次合并区间 [i, j] 时，一定是将 [i, k] 合并成的一堆与 [k+1, j] 合并成的一堆进行合并（i ≤ k < j）。
合并的得分是：
(sumW[i][k] + sumW[k+1][j]) * (sumV[i][k] + sumV[k+1][j]) 吗？
不对！因为合并时刻，左右两堆各自已经是合并后的一堆，它们的重量就是 sumW[i][k] 和 sumW[k+1][j]，权值就是 sumV[i][k] 和 sumV[k+1][j]，所以得分就是：
sumW[i][k] * sumV[k+1][j] + sumW[k+1][j] * sumV[i][k]？让我们展开：
得分 = (sumW[i][k] + sumW[k+1][j]) * (sumV[i][k] + sumV[k+1][j])
= sumW[i][k]sumV[i][k] + sumW[i][k]sumV[k+1][j] + sumW[k+1][j]sumV[i][k] + sumW[k+1][j]sumV[k+1][j]
但 sumW[i][k]sumV[i][k] 并不是 dp[i][k] 的得分总和，dp[i][k] 是区间 [i,k] 内部合并得到的总得分，最后合并成的一堆重量为 sumW[i][k]，权值为 sumV[i][k]，但没有一项得分是 sumW[i][k]sumV[i][k]。
所以不能直接这样拆。
实际上，最后一步合并的得分是：
(sumW[i][k] + sumW[k+1][j]) * (sumV[i][k] + sumV[k+1][j])
= (sumW[i][k] + sumW[k+1][j])*(sumV[i][k] + sumV[k+1][j])
这是没有问题的，这就是最后一步的得分。
那么 dp[i][j] = max over k of { dp[i][k] + dp[k+1][j] + 最后一步得分 }。
注意：dp[i][k] 是 [i,k] 内部合并的最大得分，它不影响总重量和总权值，只影响内部得分累加。
同理 dp[k+1][j] 是 [k+1,j] 内部的最大得分。
所以状态转移方程为：
dp[i][j] = max{ dp[i][k] + dp[k+1][j] + (sumW[i][k] + sumW[k+1][j]) * (sumV[i][k] + sumV[k+1][j]) }
其中 i ≤ k < j。
步骤 4：初始化
当区间长度 len = 1 时，只有一堆石子，不需要合并，得分 = 0。
所以 dp[i][i] = 0。
当区间长度 len = 2 时，只有一种合并方式，k 只能等于 i，
dp[i][i+1] = 0 + 0 + (w[i] + w[i+1]) * (v[i] + v[i+1])。
为了快速求 sumW 和 sumV，我们可以用前缀和数组：
prefixW[t] = sum(w[0..t-1])，则 sumW[i][j] = prefixW[j+1] - prefixW[i]。
同理 prefixV[t] = sum(v[0..t-1])。
步骤 5：计算顺序
按照区间长度 len 从小到大计算，len 从 2 到 n。
对于每个 len，枚举起点 i，则 j = i + len - 1。
枚举分割点 k 从 i 到 j-1。
步骤 6：最终答案
dp[0][n-1] 就是将整个区间合并成一堆的最大总得分。
步骤 7：示例推演
用示例 n=3, w=[2,3,4], v=[1,-1,2] 来验证。
前缀和 weight:
pw[0]=0, pw[1]=2, pw[2]=5, pw[3]=9。
sumW[0][0]=2, sumW[0][1]=5, sumW[0][2]=9, sumW[1][1]=3, sumW[1][2]=7, sumW[2][2]=4。
前缀和 value:
pv[0]=0, pv[1]=1, pv[2]=0, pv[3]=2。
sumV[0][0]=1, sumV[0][1]=0, sumV[0][2]=2, sumV[1][1]=-1, sumV[1][2]=1, sumV[2][2]=2。
初始化 dp[i][i]=0。
len=2:
dp[0][1] = dp[0][0]+dp[1][1]+(sumW[0][0]+sumW[1][1])(sumV[0][0]+sumV[1][1])
= 0+0+(2+3)(1+(-1)) = 50=0。
dp[1][2] = 0+0+(3+4)((-1)+2) = 7*1=7。
len=3:
i=0,j=2
k=0: dp[0][0]+dp[1][2]+(sumW[0][0]+sumW[1][2])(sumV[0][0]+sumV[1][2])
= 0+7+(2+7)(1+1) = 7+92=25。
k=1: dp[0][1]+dp[2][2]+(sumW[0][1]+sumW[2][2])(sumV[0][1]+sumV[2][2])
= 0+0+(5+4)(0+2)=92=18。
max(25,18) = 25。
所以最大得分是 25。
之前示例的第二种顺序（先合并后两堆再合并前一堆）能得到 25 吗？
先合并后两堆：
合并 (3,4): 得分=(3+4)(-1+2)=71=7，新堆重量=7，权值=1，序列变为 [2,7] 和 [1,1]。
合并 (2,7): 得分=(2+7)(1+1)=92=18，总得分=7+18=25。
是的，符合 DP 结果。
总结
这个题目的区间 DP 状态定义清晰，关键是理解合并的得分公式和区间合并时的可加性。
转移方程利用了最后一步合并的得分计算，并分解为左右子区间的 dp 值加上最后一步得分。
计算时注意前缀和预处理以便 O(1) 得到区间重量和与权值和。
时间复杂度 O(n³)，空间复杂度 O(n²)。