学习小组 题解

题目分析

将 $n$ 名同学划分为若干个学习小组，每名同学恰好属于一个小组。第 $i$ 名同学有发言积极度 $c_i$。

对于一个包含 $k$ 名同学的小组，其综合讨论积极度为：

其中 $a_k$ 是大小为 $k$ 的小组的基础分，$\max\{c\} - \min\{c\}$ 是组内最大发言积极度与最小发言积极度之差。

我们需要计算所有划分方案中，各组综合讨论积极度之和的最大值。

数据范围：$n \le 300$，$c_i, a_i \le 10^4$。

解题思路

1. 极差贡献的结构

注意到，一个小组的“极差”部分只与组内的最大值和最小值有关，与中间的其他人无关。因此，若我们将所有同学的 $c_i$ 从小到大排序，那么任何小组的极差就是它覆盖的某个区间两端点的差值。

为了最大化所有组的极差之和，我们应该让每个大小大于 $1$ 的小组“占据”当前可选的最大值和最小值。具体来说：

• 假设有 $m$ 个大小大于 $1$ 的小组，它们需要使用 $m$ 个最大值和 $m$ 个最小值，且不能重叠。
• 为了使极差总和最大，应当让第 $1$ 个这样的小组拿走全局最大值和全局最小值，第 $2$ 个拿走次大值和次小值，以此类推。
• 大小为 $1$ 的小组不贡献极差，它们可以使用剩下的中间元素，或者不参与极值对的分配。

设排序后的 $c$ 数组为 $c_1 \le c_2 \le \dots \le c_n$。如果我们最终有 $j$ 个大小大于 $1$ 的小组，那么它们贡献的总极差为：

2. 问题的转化

原问题转化为：把 $n$ 个人分成若干小组，设其中大小大于 $1$ 的组数为 $m$，大小等于 $1$ 的组数为 $s$。我们需要最大化：

同时满足总人数和为 $n$，且每个大小大于 $1$ 的组至少需要 $2$ 人。

这类似于一个“分组背包”问题：我们要选择若干个“物品”（小组），每个物品有大小（人数）和价值（$a_{size}$ 加上可能附带的极差）。但极差部分的价值并不固定，它取决于该组是第几个被加入的“大组”。由于极差随序号递减，为了让总和最大，我们显然应该先选所有大小大于 $1$ 的组（享受较大的极差），再选大小为 $1$ 的组（极差为 $0$）。

3. 动态规划

我们可以用动态规划来模拟这个“依次添加小组”的过程，并让大小大于 $1$ 的组自动获得对应序号的极差。

状态定义：

$f[j][k]$ 表示已经划分了 $j$ 个小组，这些小组共覆盖了 $k$ 名同学时，综合讨论积极度之和的最大值。

转移：

枚举最后一个加入的小组的大小 $i$（$1 \le i \le n$）。这个小组是新加入的第 $j$ 个组。

• 若 $i>1$：该小组会消耗一对极值，并获得第 $j$ 对极差，即 $c_{n-j+1} - c_j$。
• 若 $i = 1$：极差贡献为 $0$。

因此转移方程为：

其中

初始化：$f[0][0] = 0$，其余状态设为极小的负数（或利用 $a_i, c_i$ 非负，直接用 $0$ 初始化，但需注意状态可达性；数据保证所有 $a_i, c_i \ge 0$ 且方案总是存在，用 $0$ 初始化不影响最大值）。

最终答案：所有满足 $k = n$ 的状态 $f[j][n]$ 的最大值：

循环顺序：

需要保证在计算 $f[j][k]$ 时，$f[j-1][*]$ 已经包含了使用任意大小小组的所有可能性。我们可以将小组大小 $i$ 的枚举放在最外层，让组数 $j$ 递增，人数 $k$ 内层。这样等同于依次决定第 $1$ 个组、第 $2$ 个组……的大小。由于 DP 会尝试所有可能的顺序，最优方案（先放大组，后放大小为 $1$ 的组）自然会被找到。

算法说明

1. 读入 $n$，$c[]$，$a[]$。
2. 对 $c$ 进行升序排序。
3. 三层循环：
   • 最外层枚举小组大小 $i$（通常从 $n$ 到 $1$ 或 $1$ 到 $n$ 均可）。
   • 第二层枚举当前总组数 $j$（$1 \sim n$）。
   • 最内层枚举当前总人数 $k$（$i \sim n$）。
4. 按转移方程更新 $f[j][k]$，并在 $k == n$ 时更新答案。
5. 输出答案。

关于 $c$ 下标：由于排序后极差为 $c_{n-j+1} - c_j$，需要保证 $n-j+1 \ge j$ 差值才非负。在最优解中，大小大于 $1$ 的组数不会超过 $\lfloor n/2 \rfloor$，因此 $j$ 超出范围时差值非正，DP 取 $\max$ 会自然忽略这些方案。

时间复杂度

• 状态数：$O(n^2)$

• 转移：枚举 $i$，每个状态转移 $O(n)$

• 总时间复杂度：$O(n^3)$，$n \le 300$ 时约 $2.7 \times 10^7$ 次运算，可以在 $1000\text{ms}$ 内通过。

• 空间复杂度：$O(n^2)$。

参考代码

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 305;
6int n;
7int c[N], a[N];
8int f[N][N];   // f[j][k] : j 个小组，共 k 人，的最大综合积极度
9int ans;
10
11int main() {
12    scanf("%d", &n);
13    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
14    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
15    
16    sort(c + 1, c + n + 1);          // 对发言积极度排序
17    
18    // 初始化（全局变量默认0，也可显式设 -INF，但本题非负可直接用0）
19    for (int i = n; i >= 1; i--) {   // 枚举小组大小 i
20        for (int j = 1; j <= n; j++) {      // 当前总组数
21            for (int k = i; k <= n; k++) {  // 当前总人数
22                int diff = 0;
23                if (i > 1) {
24                    diff = c[n - j + 1] - c[j]; // 第 j 对极差
25                }
26                // 转移：加入一个大小为 i 的第 j 个小组
27                f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff);
28                if (k == n) {
29                    ans = max(ans, f[j][k]);   // 人数满 n 时更新答案
30                }
31            }
32        }
33    }
34    
35    printf("%d\n", ans);
36    return 0;
37}

代码说明：

• 第 17 行：sort 将 $c$ 从小到大排序，便于计算极差。
• 第 20 行：i 从 $n$ 到 $1$ 枚举小组大小。顺序不影响最终正确性，从大到小或从小到大均可。
• 第 24 行：计算 diff。当小组大小 $i>1$ 时，利用第 $j$ 对极值；$i=1$ 时没有极差。
• 第 27 行：核心转移，继承前 $j-1$ 个小组、共 $k-i$ 人的最优解，加上当前小组的贡献。
• 第 28~30 行：当人数恰好达到 $n$ 时，用当前状态更新全局答案。

总结

本题的关键在于洞察极差贡献的本质——排序后，极差仅由小组占据的若干个“极值对”产生，且这些极值对应当从大到小依次分配给各个大小大于 $1$ 的小组。通过动态规划模拟“逐个添加小组”的过程，我们可以自然地将极差与组序号绑定，并利用最优子结构求出最大综合积极度。$O(n^3)$ 的 DP 在 $n=300$ 的范围内足以通过。