学习小组 II

将 n 名同学划分为若干个学习小组，每个小组的综合积极度由基础积极度 a_k 加上组内发言积极度最大值与最小值之差组成，要求求出所有划分方案中各小组综合积极度之和的最大值。

December 1, 2025题库2分钟阅读

班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以 $1,2,\ldots,n$ 编号，第 $i$ 名同学有其发言积极度 $c_i$ 。

观察发现，如果一个学习小组中恰好包含编号为 $p_1,p_2,\ldots,p_k$ 的 $k$ 名同学，则该学习小组的基础讨论积极度为 $a_k$ ，综合讨论积极度为 $a_k+\max\{c_{p_1},c_{p_2},\ldots,c_{p_k}\}−\min\{c_{p_1},c_{p_2},\ldots,c_{p_k}\}$ ，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。

给定基础讨论积极度 $a_1,a_2,\ldots,a_n$ ，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。

输入格式

第一行，一个正整数 $n$ ，表示班级人数。

第二行， $n$ 个非负整数 $c_1,c_2,\ldots,c_n$ ，表示每位同学的发言积极度。

第三行， $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ，表示不同人数学习小组的基础讨论积极度。

输出格式

输出一行，一个整数，表示所有划分方案中，学习小组综合讨论积极度之和的最大值。

输入输出样例 #1

输入 #1
4
2 1 3 2
1 5 6 3
输出 #1
12
输入输出样例 #2

输入 #2
8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4
输出 #2
21
说明/提示

对于 $40\%$ 的测试点，保证 $c_i=0$ 。

对于所有测试点，保证 $1\le n\le 300$ ， $0\le c_i\le 10^4$ ， $0\le a_i\le 10^4$ 。

在“学习小组 I”中，我们面对的是一个纯粹的完全背包问题。这里的价值来源单一：每个小组仅取决于其规模 $k$ 所带来的固定积极度 $a_k$ 。此时，我们的目标是在 $n$ 名同学的总人数限制下，通过划分小组来最大化基础收益。其核心在于通过简单的 DP 状态转移 dp[j] = max(dp[j], dp[j-k] + a[k]) 来处理人数资源。

“学习小组 II”则是在此基础上进行的深度升级。虽然它依然保留了“基础积极度”，但引入了更复杂的极差红利。

变化点：价值不再仅仅由规模 $i$ 决定，还与“已形成小组的总数 $k$ ”深度耦合。
思维跨越：这迫使我们从“一维背包（仅看人数）”进化为“多维动态规划（同时看人数 $j$ 与组数 $k$ ）”。

理解了“学习小组 I”与“学习小组 II”的差异后，我们面临的最大挑战是如何处理“极差红利”。如果我们陷入“每个小组该如何分配成员”的细节，问题将陷入指数级的组合爆炸。

然而，通过对分组本质的数学剥离，我们可以将复杂的“分组决策”转化为精简的“极值点选取”。为了实现这一转化，我们可以通过观察数据分布，归纳出两个至关重要的数学结论：

c 部分贡献 = $\max - \min$ 。无论这个小组有 10 个人还是 100 个人，只有最积极的那个人（ $\max$ ）和最不积极的那个人（ $\min$ ）决定了小组的极差。

在构建 DP 时，我们不需要关心小组里具体有多少人，以及中间的人是谁。我们只需要确保：

我们选出了一个 max。
我们选出了一个 min。
其他位置可以用任何“边角料”人数填充，而不影响极差得分。

若我们将 $N$ 名学生划分为 $k$ 个“有效组”（即人数 $>1$ 的小组），那么所有小组的极差之和，在数学上恒等于整个序列中发言最积极的前 $k$ 人之和，减去最不积极的前 $k$ 人之和。

这一结论的意义在于：它将复杂的“组内配对”问题，简化为“极值点的选取”问题。我们无需纠结具体的配对细节，只需关注最终提取了多少个“极值对”。

我们可以通过反证法证明该结论的稳健性：

假设存在一种分组方案，其 $k$ 个组的极差之和不等于“前 $k$ 大之和减去前 $k$ 小之和”。这意味着：

大数被浪费：存在某些组的 $\max$ 值并非当前剩余序列中的最大值。
小数被浪费：存在某些组的 $\min$ 值并非当前剩余序列中的最小值。

一旦出现上述情况，我们总能通过元素交换进行优化：将当前序列中未被利用的更优大数换入 $\max$ 位置，或将更优小数换入 $\min$ 位置。由于替换后极差之和必然增加，说明原方案非最优。

由此得证： 在最优解中，每一组的 $\max$ 和 $\min$ 必然由当前剩余的全局极值组成，从而保证了极差之和的全局最大化。

我们将原先复杂的“组合优化”问题，转化为“多维资源分配的动态规划”问题。其核心逻辑在于将“分组人数”与“极差红利”进行维度解耦。

在进行任何 DP 计算之前，必须对学生积极度数组 $c$ 进行升序排序。

我们的贪心结论（极差贡献取决于序列两端）高度依赖于数组的有序性。只有 sort(c + 1, c + n + 1) 之后，c[n - k + 1] 才能精确锁定序列中第 $k$ 大的数，c[k] 才能锁定第 $k$ 小的数。没有这一步，后续的“极差红利”计算将彻底失效。

我们将总人数 $N$ 视为“背包容量”，每一个“真小组”视为“物品”。

空间成本：该组人数 $i$ 。
基础价值：组内基础积极度 $a[i]$ 。
动态红利：与小组累计个数 $k$ 挂钩的极差贡献（贪心策略）。

:::note 真小组：指人数 $> 1$ 的小组。这些小组在机制上能够产生“极差红利”。因为极差需要有至少两个数值（最大值和最小值）才能定义，所以只有人数大于 1 的组，才具备“贡献极差分”的资格。 :::

在完成排序后，利用数组 $c$ 的单调性，锁定“极差贡献”的边际递增规律：

核心规则：第 $k$ 个形成的“真小组”，必然获取序列中当前剩余的最大值（第 $k$ 大）与最小值（第 $k$ 小）的差值。
状态简化：diff = c[n - k + 1] - c[k]。此公式将极差贡献转化为仅与小组个数 $k$ 有关的静态参数。

定义状态 dp[j][k] 表示：使用 $j$ 个人，组成 $k$ 个真小组时的最大得分。

DP 底座：预处理单人组（ $k=0$ 的特殊情况）。由于单人组无极差贡献，其总得分为 dp[i][0] = i * a[1]，这构成了后续动态转移的基准。

算法的核心在于枚举三种维度，通过状态转移将“单人组”演化为“真小组”：

小组规模枚举（ $i$ ）：由外向内，依次考虑所有可能的“真小组”大小（从 2 到 $n$ ）。
容量枚举（ $j$ ）：遍历当前的可用总人数。
小组数枚举（ $k$ ）：遍历当前累计的真小组个数。

变量含义

变量	含义	取值范围	物理意义
$i$	小组规模	$2 \sim n$	你当前正在尝试“制造”哪种规格的“真小组”。
$j$	总人数	$i \sim n$	截止目前，你手里总共用了多少个人来分配。
$k$	小组数	$1 \sim j/2$	在这 $j$ 个人中，你一共挑出了多少个“真小组”。

核心转移方程：

$dp[j][k] = \max(dp[j][k], dp[j - i][k - 1] + a[i] + (c[n - k + 1] - c[k]))$

该方程的物理含义是：“在已组成 $k-1$ 个真小组的基础上，投入 $i$ 个人新建一个小组，是否能获得比当前方案更高的收益？”

由于题目未指定真小组的精确数量，最终最优得分是所有可行 $k$ 值下的最大值：

$\text{Result} = \max_{0 \le k \le n/2} \{ dp[n][k] \}$

我的 DP 代码里并没有写代码处理单人组与多人组混合的情况，程序怎么知道怎么混搭？

答案是：系统隐式覆盖。

当你进行 dp[j][k] = dp[j-i][k-1] + ... 转移时，本质上是在从全单人组（ $k-1=0$ ）或已有的混合方案中，将其中的 $i$ 个人“升级”为真小组。

这种“升级”机制保证了最终模型能遍历所有“单人组+多人组”的排列组合，实现了对所有可行分配方案的完全覆盖。

假设总人数 $n=5$ ，当前外层循环执行到 $i=3$ （尝试组建大小为 3 的组）：

当程序来到 $j=5, k=1$ 时：

逻辑起点：程序查看 dp[5-3][1-1] 即 dp[2][0]。
含义：该状态表示“用 2 个人，0 个真小组（即全是单人组）”。
决策执行：
1. 继承 dp[2][0] 的分数（单人组基础分）。
2. 加上新增大小为 3 的小组的基础分 a[3]。
3. 加上该小组带来的“极差红利”（因为 $k=1$ ，即为 c[5]-c[1]）。
结果：更新 dp[5][1]，该值记录了“5 个人中存在 1 个真小组的最大得分”。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 305;
long long dp[N][N]; // dp[总人数][真小组数]
int c[N], a[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> a[i];

    sort(c + 1, c + 1 + n);

    // 1. 初始化为 0
    memset(dp, 0, sizeof(dp));

    // 2. 预处理单人组：只有真小组数为 0 的情况
    // 题目中单人组处理：人数 i 从 1 开始遍历，价值是 i * a[1]
    for (int i = 1; i <= n; i++) {
        dp[i][0] = (long long)i * a[1];
    }

    // 3. 背包 DP
    // i: 当前真小组的人数 (从 2 开始，因为真小组至少 2 人)
    for (int i = 2; i <= n; i++) {
        // j: 背包容量（总人数），必须从 i 开始，因为只有至少 i 个人才能组建这个大小为 i 的小组
        for (int j = i; j <= n; j++) {
            // k: 真小组数量
            for (int k = 1; k <= j / 2; k++) {
                // 核心转移：因为已经初始化为 0，这里逻辑上需要保证 dp[j-i][k-1] 是有意义的方案
                // 只有当 j-i 个人确实能组成 k-1 个小组时，才进行转移
                if (dp[j - i][k - 1] > 0 || (j-i == 0 && k-1 == 0)) {
                    long long diff = (long long)c[n - k + 1] - c[k];
                    dp[j][k] = max(dp[j][k], dp[j - i][k - 1] + a[i] + diff);
                }
            }
        }
    }

    // 4. 获取答案
    long long ans = 0;
    for (int k = 0; k <= n / 2; k++) {
        ans = max(ans, dp[n][k]);
    }

    cout << ans << endl;
    return 0;
}

:::caution

在编写 DP 代码时，务必注意 if 条件中的状态合法性检查： if (dp[j - i][k - 1] > 0 || (j - i == 0 && k - 1 == 0))

这里包含两层含义：

dp[j - i][k - 1] > 0：这是对“历史状态”的合法性校验，确保当前决策是基于一个已经成型且有效的分组方案，防止在不可达的逻辑空间中进行无效计算。
(j - i == 0 && k - 1 == 0)：这是对“原点”的保护。它是算法运行的启动条件，确保了当我们在组建第一个“真小组”时，系统能从总人数为 0、小组数为 0 的初始状态平滑过渡。

:::