一、原题描述


二、题目解析
1. 故事背景
班主任要把全班同学分成学习小组。
- 一共 n 个同学
- 每个同学都有一个发言积极度
- 每个学习小组要求:
- 所有人必须被分进去
- 不能重叠
2. 分数计算规则
每个学习小组的得分由两部分组成:
(1) 基础讨论积极度
只和小组人数有关。人数是 k,就加 a[k]。
(2) 额外热闹值
小组里最爱说话的同学(最大值)与最不爱说话的同学(最小值)之差。
公式:额外值 = 最大 - 最小
3. 目标
想办法分组,让所有小组的综合讨论积极度之和最大。
4. 示例分析
假设有 4 个同学,编号 1 到 4,积极度分别为 2, 1, 3, 2。 基础分数组 a 为:a[1]=1, a[2]=5, a[3]=6, a[4]=3。
-
方案一:每人一组
- [2], [1], [3], [2]
- 每组基础分 = a[1] = 1,额外值 = 0
- 总分 = 4
-
方案二:全班一组
- [2, 1, 3, 2]
- 基础分 = a[4] = 3
- 最大 = 3,最小 = 1,额外 = 2
- 总分 = 5
-
方案三:分成两组
- [2, 1], [3, 2]
- 第一组:基础 = 5,差值 = 2 - 1 = 1
- 第二组:基础 = 5,差值 = 3 - 2 = 1
- 总分 = 12
5. 解题思路
暴力枚举所有分组方式会导致方案数爆炸,因此必须使用动态规划(DP)。
(1) 排序的重要性
在 DP 之前需要先对积极度进行排序:sort(c + 1, c + n + 1)。
排序后,最小值在前,最大值在后,方便计算 最大 - 最小。
核心结论:如果目标是最大化差值,一定要把最小的和最大的放在同一组。中间的人是谁,对差值没有影响。
(2) DP 状态定义
f[j][k] 表示用 k 个同学分成 j 个小组能得到的最大综合讨论积极度。
(3) 状态转移
假设最后一个小组有 i 个人,前面用了 k - i 个同学,前面有 j - 1 个小组。 转移公式:


