北京海淀区信息学竞赛 · 2024 北京市海淀区信息学竞赛（初赛）试题 第 20 题

定义一个序列的 美丽度 为这个序列中最大的三个元素的总和。

现有一个序列 $\{5, 2, 5, 2, 4, 1, 1, 3, 2, 6, 4, 4, 5, 6, 2, 2\}$，请你将这个序列恰好划分为 $4$ 个子序列，每个序列长度都不小于 $3$，原序列中的每个元素都在某一个子序列中，且每个子序列都是由原序列中的连续元素构成，则这 $4$ 个子序列的 美丽度 之和最大值为（ ）

这题本质是贪心：把序列切成长度≥3的段，每段取最大的三个数求和。要让总和最大，直觉是把大的数尽量凑在一起，让每段都能“吃”到三个大数；而把小的数单独拉出去凑段，避免它们占用大数名额。

最容易错在把大数分散到不同段，导致每段只能吃到两个大数，总和反而变小；或者为了凑段数把几个大数强行塞进同一段，结果那段长度不够，不得不把大数拆散。还有一种坑是只盯着局部最优，没算好剩余元素能不能凑出第四段。

题目要求把原序列恰好分成4段，每段长度≥3，每段的美丽度定义为该段中最大的三个元素之和，求4段美丽度之和的最大值。

先数一下：序列共16个元素，分成4段，每段平均长度4，完全可行。

贪心策略：为了让每段都吃到三个大数，我们应该尽量把大的数聚在一起，形成“大数段”；然后把剩下的小数凑成“小数段”，这样大数段里三个最大数都能被计入，而小数段里最大的三个数相对较小，对总和贡献有限。

原序列排序后是：6,6,5,5,5,4,4,4,3,2,2,2,2,1,1,1。我们按原顺序看，前几个大数是6,6,5,5,5，后面跟着4,4,4,3,2,2,2,2,1,1,1。

尝试构造：

• 第一段：取前4个元素 {5,2,5,2}，最大三个是5,5,2，和为12。
• 第二段：接着取4个 {4,1,1,3}，最大三个是4,3,1，和为8。
• 第三段：再取4个 {2,6,4,4}，最大三个是6,4,4，和为14。
• 第四段：最后4个 {5,6,2,2}，最大三个是6,5,2，和为13。

总和=12+8+14+13=47。

能不能更大？如果尝试把两个6放在同一段，比如第一段取{6,5,2,5}，最大三个6,5,5和为16，但这样会消耗掉两个6和一个5，剩下的大数就少了，后续段很难再凑出三个大数，总和反而下降。如果把6分散到不同段，每段最多只能吃到一个6，总和也会减少。

再验证一下长度约束：每段都是4个元素，满足≥3的要求；总共16个元素，正好用完。

所以最大值就是47，对应选项D。