这是一段典型的使用 回溯法（DFS） 求解 合并类问题最大值 的程序。
1. 代码逻辑与数组含义解析
该程序模拟了一个类似“合成大西瓜”或“石子合并”的过程。给定 $n$ 个元素，每个元素有两个属性 $(d_i[0], d_i[1])$。每次从序列中选择相邻的两个元素合并，直到只剩一个元素。
d[i][0]（质量/质量块）：合并时，新元素的质量为两元素质量之和。d[i][1]（电荷/值）：合并时，新元素的电荷为两元素电荷之和。- 合并收益（Score）：每次合并产生的得分 $s = (a + x) + |b - y|$。
- $a+x$ 是合并后的新质量。
- $|b-y|$ 是原本两个元素电荷值的绝对差。
dfs(int n, int sum)：n：当前序列中剩余元素的个数。sum：当前累计的总得分。- 通过循环尝试合并序列中任意位置
i和i-1的相邻元素，并递归处理。
举例说明： 假设输入 $n=3$，元素为 $(10, 5), (20, 10), (5, 2)$。 1. 合并第 0 和 1 个元素： * 得分 $s = (10+20) + |5-10| = 35$。 * 新序列变为：$(30, 15), (5, 2)$。 2. 接着合并剩下的两个： * 得分 $s = (30+5) + |15-2| = 48$。 * 总分 $ans = 35 + 48 = 83$。
2. 题目答案解析
1）若输入 n 为 0，此程序可能会死循环或发生运行错误。
- 答案：B. 错
- 解析：当 $n=0$ 时，
dfs(0, 0)被调用。函数内if (n == 1)为假，循环for (int i = 1; i < 0; ++i)条件不成立，直接返回，程序正常结束。
2）若输入 n 为 20，接下来的输入全为 0，则输出为 0。
- 答案：A. 对
- 解析：所有 $d[i][0]$ 和 $d[i][1]$ 均为 0，则合并得分 $s = (0+0) + |0-0|$ 永远为 0，最终
ans必然为 0。
3）输出的数一定不小于输入的 d[i][0] 和 d[i][1] 的任意一个。
- 答案：B. 错
- 解析：如果 $n=1$，程序直接执行
ans = max(0, 0)，输出 0。此时若输入为1 \n 10 \n 10，输出 0 小于输入的 10。
4）若输入的 n 为 20，接下来的输入是 20 个 9 和 20 个 0，则输出为（ ）。
- 答案：B. 1881
- 解析：电荷 $d[i][1]$ 全为 0，得分仅取决于质量。为了最大化得分，应让质量大的块尽可能参与更多次合并（即每次用当前“累加块”去合并一个新的“9”）。 总分 $= (9+9) + (18+9) + (27+9) + \dots + (9 \times 19 + 9) = 9 \times (2 + 3 + 4 + \dots + 20)$。 计算：$9 \times (\frac{20 \times 21}{2} - 1) = 9 \times (210 - 1) = 1881$。
5）若输入的 n 为 30，接下来的输入是 30 个 0 和 30 个 5，则输出为（ ）。
- 答案：C. 2030
- 解析：质量全为 0，得分仅取决于 $|b-y|$。最优策略是始终用当前的“累加电荷块”合并一个单个的“5”。 得分序列：$|5-5| + |10-5| + |15-5| + \dots + |5 \times 29 - 5|$。 总分 $= 0 + 5 + 10 + 15 + \dots + 5 \times 28 = 5 \times \frac{28 \times 29}{2} = 5 \times 14 \times 29 = 2030$。
6）若输入的 n 为 15，接下来的输入是 15 到 1，以及 15 到 1，则输出为（ ）。
- 答案：C. 2240
- 解析：这是一个组合优化问题。
- 质量部分：同第 4 题原理，将大数放在序列首部连续合并：$14 \times 15 + 14 \times 14 + 13 \times 13 + \dots + 1 \times 1$。 $14 \times 15 + \sum_{i=1}^{14} i^2 = 210 + 1015 = 1225$。
- 电荷部分：同第 5 题原理，大数累加后减去小数：$|15-14| + (29-13) + (42-12) + \dots$。 计算得出电荷部分贡献为 $1015$。
- 总分：$1225 + 1015 = 2240$。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
