CSP-S 2026 第一轮 第 6 题：有 5 堆石子排成一行，重量依次为 4

题目

有 5 堆石子排成一行，重量依次为 4、1、3、2、5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。

选项

• A. 36
• B. 35
• C. 34
• D. 33

答案

C

题解

答案是 C．34。

一种合并方法如下（括号内是本次代价）：

1. 合并中间的 1、3：变成 4、4、2、5，代价 4。
2. 合并左边的 4、4：变成 8、2、5，代价 8。
3. 合并右边的 2、5：变成 8、7，代价 7。
4. 合并 8、7：变成 15，代价 15。

总代价为： \[ 4+8+7+15=\boxed{34} \]

怎样确认它最小？ 最后一次合并的代价一定是全部重量之和 15。由于只能合并相邻的堆，最后两堆必然对应原序列的左右两段。枚举分界位置：

表中各段的最小代价，也可以用同样的“枚举最后分界”方法算出。这就是区间动态规划的思路。