GESP 题解库 / 7 级题解 / [GESP202512 七级] 学习小组 · 第 3 / 24 题
GESP202512 七级 · P14922 · 困难

学习小组

把组内极差抽出来(Q(m) − P(m)),其余部分用 DP 求 Σa_k。

👥
n ≤ 300
学生人数
📈
cᵢ, aᵢ ≤ 10⁴
积极度上限
⚡
O(n³)
时间复杂度
🎯
排序引理 + 分组 DP
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

把 n 名同学划分成若干个学习小组,每人恰好属于一个组。若一个组恰好包含 k 名同学,则它的基础讨论积极度为 a_k,综合讨论积极度为

a_k + (组内最大的 c − 组内最小的 c)

给定 a₁, a₂, …, a_n 与每人的 cᵢ,求所有划分方案中综合积极度之和的最大值。

💡
人话翻译:难点全在"组内极差"上——它看起来依赖"具体怎么分组"。
突破口是一条引理:设人数 ≥ 2 的小组共有 m 个,那么 Σ(组内极差) 的最大值只取决于 m:
Σ(极差) ≤ Q(m) − P(m),其中 Q(m) 是最大的 m 个 c 之和、P(m) 是最小的 m 个 c 之和。
因为可以让"最大的 m 个 c"分别当各组的最大值、"最小的 m 个 c"分别当各组的最小值,其余同学随便塞进组里,既不改变最大值也不改变最小值。
于是极差贡献被"抽干"了,剩下的 Σa_k 只要做一个"组数 × 总人数"的 DP 就行。

🔍 关键词提取

划分型问题极差可分离排序引理分组 DPO(n³)

已知条件

项目说明
输入第一行 n;第二行 n 个 cᵢ;第三行 n 个 aᵢ
输出综合积极度之和的最大值
数据范围1 ≤ n ≤ 300
数值范围0 ≤ cᵢ ≤ 10⁴,0 ≤ aᵢ ≤ 10⁴
部分分40% 的测试点保证 cᵢ = 0
组的形态人数 = 组大小 k,贡献查 a_k

需要解决的问题

02
思维导图
整理解题思路的全貌
👥 极差 = 组内 max − 组内 min,可以分离
🧠 关键引理
设人数 ≥ 2 的组共 m 个
Σ(组内极差) 的最大值 = Q(m) − P(m)
Q(m):最大的 m 个 c 之和
P(m):最小的 m 个 c 之和
🔁 为什么成立
最大的 m 个 c 各当一个组的 max
最小的 m 个 c 各当一个组的 min
中间元素随便塞,不影响 max / min
所以极差贡献与"具体怎么分组"无关
📐 DP 部分
dp[m][S] = 恰好 m 个"≥2 人的组"、总人数 S 时 Σa_k 最大
转移:dp[m][S] = max(dp[m−1][S−k] + a_k),k ≥ 2
单人组共 (n−S) 个,各贡献 a₁
答案 = max( dp[m][S] + (n−S)·a₁ + Q(m) − P(m) )
⚠️ 易错点
用"排序后连续区间 DP"(样例 2 只得 17)
极差项写成 Q(m) + P(m)
漏掉 m = 0(全员单人组)的情形
给单人组也算极差
03
样例手算推导
两个样例的完整推演(含错解对比)

🧮 样例 1:n = 4,答案 12

c = [2, 1, 3, 2],a = [1, 5, 6, 3](即 a₁=1, a₂=5, a₃=6, a₄=3)。排序后 c = [1, 2, 2, 3]。

划分方案各组的 (a_k + 极差)总和
4 个单人组1 + 1 + 1 + 1(极差全为 0)4
一个 2 人组 + 2 个单人组(5 + 1) + 1 + 18
两个 2 人组(最优)(5 + 1) + (5 + 1)12
一个 3 人组 + 1 个单人组(6 + 2) + 19
一个 4 人组3 + 25
1
最优方案长什么样

组一:同学 1(c=2)与同学 2(c=1)→ 5 + (2 − 1) = 6

组二:同学 3(c=3)与同学 4(c=2)→ 5 + (3 − 2) = 6

合计 12

✅ 12

2
用引理核对一步

两个组都是 2 人,所以 m = 2、S = 4

dp[2][4] = a₂ + a₂ = 5 + 5 = 10

Q(2) = 3 + 2 = 5(最大的 2 个 c)

P(2) = 1 + 2 = 3(最小的 2 个 c)

极差贡献 = 5 − 3 = 2

单人组 (n − S) = 0 个

总候选值 = 10 + 0 + 2 = 12

✅ 与暴力枚举一致

🔑
注意极差贡献是 2 而不是 3:两个组各自的极差是 1 和 1,加起来正好等于 Q(2) − P(2) = 5 − 3 = 2。这不是巧合——把"每组一个最大值、每组一个最小值"全部拆开再相加,就得到"前 m 大之和 − 前 m 小之和"。

🧮 样例 2:n = 8,答案 21(以及错解为什么是 17)

c = [1, 3, 2, 4, 3, 5, 4, 6],a = [0, 2, 5, 6, 4, 3, 3, 4]。排序后 c = [1, 2, 3, 3, 4, 4, 5, 6]。

1
第 1 步:找到最优参数

最优取 m = 3(3 个"人数 ≥ 2 的组")、S = 8(没有单人组)

组大小为 3、3、2

dp[3][8] = a₃ + a₃ + a₂ = 5 + 5 + 2 = 12

Q(3) = 6 + 5 + 4 = 15(最大的 3 个 c)

P(3) = 1 + 2 + 3 = 6(最小的 3 个 c)

极差贡献 = 15 − 6 = 9

总候选值 = 12 + (8 − 8) × a₁ + 9 = 21

✅ 21

2
第 2 步:还原一个真实划分

组一:同学 1、2、4(c = 1, 3, 4)→ 5 + (4 − 1) = 8

组二:同学 3、6、7(c = 2, 5, 4)→ 5 + (5 − 2) = 8

组三:同学 5、8(c = 3, 6)→ 2 + (6 − 3) = 5

合计 8 + 8 + 5 = 21

注意"最大值"分别是 4、5、6(正好是最大的 3 个 c)

"最小值"分别是 1、2、3(正好是最小的 3 个 c)

✅ 21

❌ 错解:排序后连续区间 DP 只能得 17

方案分组(按排序后的值)各组贡献总和
连续区间 DP[1, 2, 3]、[3, 4]、[4, 5, 6](5 + 2) + (2 + 1) + (5 + 2)17
正解(排序引理 + DP)[1, 3, 4]、[2, 4, 5]、[3, 6](5 + 3) + (5 + 3) + (2 + 3)21
⚠️
为什么连续区间 DP 会少算 4 分?它强制"同一组在排序后必须相邻",于是最优秀的搭配——让 1 和 4 同组、让 3 和 6 同组——根本不可能出现。
而本题只关心组内的最大值与最小值,中间夹着哪些值完全不影响极差,所以"连续"这个额外限制是完全没必要的,只会把最优解排除在外。
记住:样例 1 两者都是 12,但样例 2 连续区间 DP 只有 17——这就是本题最经典的错解。
04
解法对比
排序引理 + DP vs 排序后连续区间 DP(错解)

⚔️ 解法对比

🟢 排序引理 + 分组 DP(推荐) 推荐

极差部分用 Q(m) − P(m) 抽干,Σa_k 部分用 dp[m][S] 求最大

  • 时间 O(n³) ≈ 1.35 × 10⁷
  • 空间 O(n²)
  • 两个样例都得 21 / 12
  • 思路可迁移到很多划分题
💡
两步分离是关键:① Σ(极差) 只跟"有几个 ≥2 人的组"有关,最大值就是 Q(m) − P(m);② Σa_k 只跟"组数 + 各组人数"有关,用 DP 求最大。
两块互不影响,所以可以分别取最优再相加。

🟠 排序后连续区间 DP

把 c 排序后,令每一组是排序数组上连续的一段

  • 时间 O(n²) 更快
  • 代码更短
  • 样例 1 恰好也是 12(有迷惑性)
  • 样例 2 只有 17
⚠️
为什么会错:它额外假设了"同组必须相邻",而题目从没要求这一点。
极差只看组内 max 与 min,中间元素是谁都无所谓;强行连续会把"跨越式搭配"排除掉,样例 2 因此少算 4 分(17 而不是 21)。

📈 性能对比

方案复杂度样例 2 的结果
排序引理 + DPO(n³) ≈ 1.35 × 10⁷✅ 21
连续区间 DPO(n²)❌ 17
暴力枚举所有划分指数级(Bell 数)❌ n = 300 完全不可行
05
算法流程图
排序 → 枚举组数 → DP 求 Σa_k → 合并极差
开始读入 n、c 数组、a 数组把 c 升序排序,求出前缀和;P(m) 取前 m 小、Q(m) 取前 m 大dp[0][0] = 0,其余 dp[m][S] = −∞对 m = 1…⌊n/2⌋、S = 2m…n:dp[m][S] = max over k ≥ 2 of ( dp[m−1][S−k] + a_k )枚举 (m, S):候选 = dp[m][S] + (n−S)·a₁ + Q(m) − P(m);m = 0 时另算 n·a₁所有 (m, S) 都比过了吗?输出最大候选值枚举下一组 (m, S)
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

👥 最大综合积极度计算器

三行输入:n / 每人的 cᵢ / 每个组大小的 aᵢ。程序会跑"排序引理 + DP",并同时显示错解(连续区间 DP)的结果作对照。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(排序引理 + 分组 DP)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int  MAXN = 305;
const ll   NEG  = -(1LL << 60);

int n;
ll c[MAXN], a[MAXN];
ll pre[MAXN];                 // pre[i]:排序后前 i 个 c 之和
ll dp[155][MAXN];             // dp[m][S]:恰好 m 个"人数>=2 的组"、总人数 S 时 Σa_k 最大

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &c[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    // 排序 + 前缀和:之后可以 O(1) 取"最小的 m 个 c 之和"与"最大的 m 个 c 之和"
    sort(c + 1, c + n + 1);
    for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + c[i];

    int maxm = n / 2;                       // "人数>=2 的组"最多 n/2 个
    for (int m = 0; m <= maxm; m++)
        for (int S = 0; S <= n; S++) dp[m][S] = NEG;
    dp[0][0] = 0;

    for (int m = 1; m <= maxm; m++)
        for (int S = 2 * m; S <= n; S++)
            for (int k = 2; k <= S; k++)
                if (dp[m - 1][S - k] != NEG)
                    dp[m][S] = max(dp[m][S], dp[m - 1][S - k] + a[k]);

    ll ans = 1LL * n * a[1];                // m = 0:全员单人组
    for (int m = 1; m <= maxm; m++)
        for (int S = 2 * m; S <= n; S++) {
            if (dp[m][S] == NEG) continue;
            ll P = pre[m];                  // 最小的 m 个 c 之和
            ll Q = pre[n] - pre[n - m];     // 最大的 m 个 c 之和
            ll val = dp[m][S] + 1LL * (n - S) * a[1] + Q - P;
            ans = max(ans, val);
        }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么极差项可以直接用 Q − P?因为 Σ(组内极差) = Σ(各组最大值) − Σ(各组最小值)。
m 个组的最大值一共是 m 个互不相同的同学,所以 Σ(最大值) ≤ Q(m);同理 Σ(最小值) ≥ P(m),于是 Σ(极差) ≤ Q(m) − P(m)。
而这个上界能同时取到:让最大的 m 个 c 分别当 m 个组的最大值、最小的 m 个 c 分别当最小值即可(中间元素随便分配,不影响 max / min)。所以不是不等式,而是等式。

📖 关键几行怎么看

代码作用为什么这样写
sort(c + 1, c + n + 1);排序排序后才能 O(1) 取前 m 小 / 前 m 大
pre[i] = pre[i-1] + c[i];前缀和Q(m) = pre[n] − pre[n−m]
dp[0][0] = 0;DP 边界0 个组、0 人时 Σa_k = 0
for (k = 2; k <= S; k++)转移组大小至少 2(单人组单独用 a₁ 算)
ans = 1LL * n * a[1];m = 0 的情形全员单人组:极差全 0,共 n·a₁
val = dp[m][S] + (n−S)·a₁ + Q − P;合并三块相加:Σa_k + 单人组贡献 + 极差贡献
⚠️
五个坑:① 用"排序后连续区间 DP"(样例 2 会得 17);② 极差项符号写成 Q + P;③ m = 0 没考虑(全单人组,答案是 n·a₁);④ 给单人组也算极差(应为 0);⑤ dp 数组第二维开小(S 要到 n,第一维要到 n/2)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
2 1 3 2
1 5 6 3
12题面样例 1
8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4
21题面样例 2(连续区间 DP 只会得 17)
1
5
7
7n = 1:只能单人组,贡献 a₁
2
0 0
1 5
5两人同组(a₂ = 5)优于两个单人组(2)
3
0 0 0
0 0 100
100c 全为 0 → 极差为 0,只看 a_k
4
5 5 5 5
1 1 1 1
4全同值:极差恒 0,拆成全单人组最优
✅
自查清单:① 用的是"排序引理 + DP"吗?② 极差项是 Q − P 吗?③ 考虑到 m = 0 了吗?④ 组大小从 2 开始枚举了吗?

🚨 易错点清单

⚠️
连续区间 DP:强制"同组在排序后相邻",样例 2 只能得 17,比正确答案 21 少 4。
⚠️
极差符号写反:是 Q(m) − P(m),不是 +。
⚠️
漏掉 m = 0:所有同学都单独成组时答案是 n · a₁,必须参与取最大。
⚠️
给单人组算极差:单人组的 max = min,极差为 0,只贡献 a₁。
⚠️
数组开小:dp 需 [n/2 + 1][n + 1]。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n³)
空间复杂度
O(n²)
n 最大
300
运算量
约 1.35 × 10⁷

时间怎么算的?

空间都用在哪?

dp 表大小 (n/2 + 1) × (n + 1) ≈ 151 × 301 ≈ 4.5 × 10⁴ 个 long long,约 360 KB;另有 c、a、pre 三个长度 n 的数组。

✅ 千万级操作,C++ 只需几十毫秒。n ≤ 300 这个规模,正是为"排序 + O(n³) 划分 DP"准备的。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 学习小组:两步分离的通用套路

// (1) 极差部分:把它"抽干"成只跟组数 m 有关的量
//     设人数 >= 2 的组共有 m 个
//     Σ(组内极差) 的最大值 = Q(m) - P(m)
//       Q(m) = 最大的 m 个 c 之和
//       P(m) = 最小的 m 个 c 之和
//     理由:让最大的 m 个 c 各当一个组的 max、最小的 m 个 c 各当一个组的 min,
//           剩下的元素塞进任意组都不改变 max / min

// (2) Σa_k 部分:分组 DP
//     dp[m][S] = 恰好 m 个"人数 >= 2 的组"、总人数 S 时 Σa_k 的最大值
//     转移:dp[m][S] = max over k >= 2 of ( dp[m-1][S-k] + a_k )
//     含义:最后一个组放 k 个人,剩下 m-1 个组占 S-k 人

// (3) 合并:剩下的 (n - S) 人各自单独成组,每组只贡献 a_1(极差为 0)
//     ans = max over (m, S) of ( dp[m][S] + (n - S) * a[1] + Q(m) - P(m) )
//     别忘了 m = 0 的情况:ans 初始化为 n * a[1]

// (4) 千万不要用"排序后连续区间 DP"
//     那强行要求同组在排序数组上连续,会把跨组的更优搭配排除掉
//     本题样例 2:连续区间 DP = 17,正确答案 = 21

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
极差可分离把 Σ(max−min) 化成 Q(m) − P(m)和式中的 max / min 只取决于"选了几个极值"
排序 + 前缀和O(1) 取"前 m 小 / 前 m 大"之和任何"取 k 个最小 / 最大"的题
分组 DPdp[m][S] 记录"组数 + 总人数"装箱、划分、凑数类问题的建模
枚举 (m, S) 合并把两块独立最优值相加先分离、再合并的优化思路
🌟
思考题:如果把每组贡献改成 a_k + 组内最大 c(只加最大值、不加最小值),排序引理还好用吗?(提示:好用。Σ(组内最大) ≤ Q(m),而且取"最大的 m 个 c 当各组最大值"就能取到等号,所以极差项换成 Q(m) 即可,DP 部分完全不用改。这类题的通用套路是:只要"组的额外贡献"只依赖组内的极值,就能把它抽出来变成"前 m 大 / 前 m 小"的组合问题。)