GESP 七级 · GESP202609 C++ 七级 第 6 题

有 4 堆石子，数量分别为 1、2、3、4。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（ ）。

看到题先想：合并代价是两堆之和，本质是构造一棵二叉树，叶子是初始石子数，内部节点权值是子树和。最小总代价=所有内部节点权值之和。这类题通法是区间DP：枚举区间长度，再枚举分割点，dp[i][j]表示合并第i到j堆的最小代价。

选项A 17 是贪心误把1+2+3+4=10当总代价；选项C 20 是合并顺序(1+2)+(3+4)再合并，代价3+7+10=20；选项D 23 是合并2+3=5后1+5=6再6+4=10，总21，但有人算错成23。最阴险的是"相邻"二字，合并后新堆位置会变，不能简单按原顺序算。

1. 考纲定位

本题考查 GESP 七级 C++ 第 4 章"动态规划"第 2 节"区间 DP"。命题人卡住的是"合并代价是两堆之和"这一非标准 DP 状态，多数考生会误用贪心或简单枚举。

2. 解题思维

先枚举所有合并顺序，算出总代价：

• 顺序 1：(1+2)=3，(3+3)=6，(6+4)=10 → 总代价 3+6+10=19
• 顺序 2：(2+3)=5，(1+5)=6，(6+4)=10 → 总代价 5+6+10=21
• 顺序 3：(3+4)=7，(3+7)=10，(1+10)=11 → 总代价 7+10+11=28
• 顺序 4：(1+2)=3，(3+4)=7，(3+7)=10 → 总代价 3+7+10=20

最小值 19，对应选项 B。