一、原题描述
二、题目解析
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 个小组。 转移公式：
