GESP 题解库 / 6 级题解 / [GESP202506 六级] 学习小组 · 第 8 / 27 题
GESP202506 六级 · P13015 · 简单

学习小组

把 n 名同学分成若干组,组内 k 人得 a_k 分,求最大总分。

📊
n ≤ 1000
班级人数
🔢
long long
分值范围
⚡
O(n²)
时间复杂度
🎯
分割型(完全背包式)DP
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

把 n 名同学划分成若干小组,每人必须属于某个组。若某个小组恰好 k 人,则该组积极度为 a_k。求所有划分方案中积极度之和的最大值。

💡
人话翻译:典型的"整数划分"型 DP。设 dp[i] 表示"把 i 名同学分组能得到的最大积极度",转移就是枚举最后分出的一组有多少人:dp[i] = max(dp[i−k] + a_k)(k 从 1 到 i)。
注意每组人数没有上限,同一种组大小可以反复使用——所以这本质上是"完全背包"式的 DP。

🔍 关键词提取

整数划分分割型 DP完全背包枚举组大小

已知条件

项目说明
输入第一行 n;第二行 a₁…aₙ
输出最大积极度之和
数据范围1 ≤ n ≤ 1000
分值范围0 ≤ aᵢ ≤ 10⁴
约束每人属于恰好一个组;组大小可重复出现

需要解决的问题

02
思维导图
整理解题思路的全貌
👥 dp[i] = max(dp[i−k] + a[k])
🧠 状态定义
dp[i]:i 个人的最大总分
dp[0] = 0(0 人得 0 分)
答案 = dp[n]
按人数递推
🔁 转移
枚举最后一组的大小 k
k 从 1 遍历到 i
dp[i] = max(dp[i−k] + a[k])
取所有合法 k 的最大值
🔍 为什么是"完全背包"
组大小可重复使用
如 n=6 可分成 2+2+2
所以 k 可以反复选
与"完全背包"结构一致
⚠️ 易错点
dp 初值没设好(应为 0,因为分值非负)
用 int(总分可达 10⁷,仍在 int 内但保险用 long long)
枚举 k 时越界
把"组数上限"错加进去
03
样例手算推导
两个样例的 dp 推演

🧮 样例 1:n = 4,a = [1, 5, 6, 3]

a₁=1、a₂=5、a₃=6、a₄=3。

1
dp[0] = 0

0 个人不需要分组

dp[0] = 0

2
dp[1]

只能分成 1 人组:dp[0] + a₁ = 0 + 1 = 1

dp[1] = 1

3
dp[2]

k = 1:一个 1 人组 → dp[1] + a₁ = 1 + 1 = 2

k = 2:一个 2 人组 → dp[0] + a₂ = 0 + 5 = 5

取最大 → 5

dp[2] = 5

4
dp[3]

k = 1:dp[2] + a₁ = 5 + 1 = 6

k = 2:dp[1] + a₂ = 1 + 5 = 6

k = 3:dp[0] + a₃ = 0 + 6 = 6

三种都是 6

dp[3] = 6

5
dp[4]

k = 1:dp[3] + 1 = 7

k = 2:dp[2] + 5 = 5 + 5 = 10

k = 3:dp[1] + 6 = 1 + 6 = 7

k = 4:dp[0] + 3 = 3

取最大 → 10

✅ dp[4] = 10

📊 dp 汇总

i01234
dp[i]015610
最优方案—121+2 或 32+2

最优划分:2 + 2 → 5 + 5 = 10 ✓

🔑
注意 "2 + 2" 里用了两次"2 人组"——这正是本题"组大小可重复"的体现。如果误以为是"每种组大小只能用一次"(0/1 背包),就会得到 2 + 1 + 1 = 7 这样的错误结果。读题时要抓住"每个小组恰好 k 人得 a_k 分",并没有说"组大小不能重复"。

🧮 样例 2:n = 8,a = [0, 2, 5, 6, 4, 3, 3, 4]

这组数据里 a₁ = 0,所以"单独成组"没有收益。

idp[i]最优最后一组大小说明
101a₁ = 0
222a₂ = 2
353a₃ = 5
464a₄ = 6
575max(dp[4]+0, dp[2]+a₃=2+5=7, a₅=4) = 7
6103 + 3dp[3] + a₃ = 5 + 5 = 10
7113 + 4dp[4] + a₃ = 6 + 5 = 11
8122 + 3 + 3dp[5] + a₃ = 7 + 5 = 12

答案 12 ✓

⚠️
注意验证 dp[8]:我们算的是 dp[5] + a₃ = 7 + 5 = 12,即"先分 5 个人(最优 7 分),再补一个 3 人组(5 分)"。
而 dp[5] = dp[2] + a₃ = 2 + 5 = 7,所以整体是"2 + 3 + 3"三组,得分 2 + 5 + 5 = 12 ✓。这种"从子问题拼出来"的过程正是 DP 的精髓。
04
解法对比
整数划分 DP vs 贪心/搜索

⚔️ 解法对比

🟢 整数划分 DP(推荐) 推荐

dp[i] 枚举最后一组大小 k,dp[i] = max(dp[i−k] + a[k])

  • 时间 O(n²) = 10⁶
  • n = 1000 时轻松通过
  • 代码 12 行
  • 空间 O(n)
💡
为什么贪心不行:如果按"每组平均分最高"贪心,比如样例 1 里 a₄/4 = 0.75 而 a₂/2 = 2.5,但真正的最优还需要考虑能否整除——a_k 并不是线性的,所以只能老老实实 DP 枚举。

🟠 搜索所有分拆方案

枚举 n 的所有整数分拆,逐一计算得分

  • 分拆数 p(1000) 天文数字
  • 完全不可行
  • n = 10 时还行(40% 测试点)
  • 不适合
⚠️
量级对比:n = 1000 的整数分拆数 p(1000) 约为 2.4 × 10³¹——比宇宙原子数还多。而 DP 只需 10⁶ 次运算,这就是"用状态压缩掉重复子问题"的威力。

📈 性能对比

方案复杂度(n = 1000)可行性
整数划分 DP约 10⁶✅ 瞬间
枚举分拆指数/天文级❌ 不可行
05
算法流程图
分割型 DP 枚举最后一组大小
开始读入 n 和数组 a;dp[0] = 0i 从 1 到 nbest = 0k 从 1 到 i(枚举最后一组的人数)best = max(best, dp[i − k] + a[k])dp[i] = best输出 dp[n]i 加 1 递推下一个人数
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

👥 最大讨论积极度

第一行输入 n,第二行输入各规模小组的积极度,程序会算出最大总和。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

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

long long a[1005], dp[1005];

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

    dp[0] = 0;                             // 0 个人得 0 分

    for (int i = 1; i <= n; i++) {
        long long best = 0;
        for (int k = 1; k <= i; k++) {      // 枚举"最后一组"的人数
            best = max(best, dp[i - k] + a[k]);
        }
        dp[i] = best;
    }

    printf("%lld\n", dp[n]);
    return 0;
}
🔑
为什么 best 初值取 0 就够?因为题目保证 a_i ≥ 0,所以"分成若干组"的总分一定 ≥ 0。
如果 a_i 可能为负,初值就要设成很小的数(如 -1e18),并且要想清楚"是否允许不分组"(题目要求每人必须分组,所以不允许)。初值的选取要结合题意,不能照抄模板。

📖 关键几行怎么看

代码作用为什么这样写
dp[0] = 0边界0 个人的总分为 0
for (k = 1; k <= i; k++)枚举组大小最后一组可以是 1 ~ i 人中的任意大小
dp[i - k] + a[k]转移前 i−k 个人的最优 + 这一组的得分
best = max(best, ...)取最优在所有分法中选最大的
⚠️
三个坑:① 误以为"每种组大小只能用一次"(那就变成 0/1 背包了);② 初值设成负无穷(本题分值非负,用 0 更简单);③ 循环边界写成 k < i(会漏掉"整组就是 i 人"的情形)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
4
1 5 6 3
10题面样例 1(2 + 2)
8
0 2 5 6 4 3 3 4
12题面样例 2(2 + 3 + 3)
1
7
7只分一组
3
0 0 0
0所有分值都是 0
6
1 1 1 1 1 1
6每种组都只值 1 分,分成 6 个单人组
6
0 0 0 0 0 100
100整组 6 人最划算
✅
自查清单:① 组大小可重复吗?② k 枚举到 i 吗?③ dp[0] = 0 吗?

🚨 易错点清单

⚠️
组大小不可重复:题目没这个限制,同一种组大小可以反复出现(如样例 1 的 2 + 2)。
⚠️
循环边界错:k 要遍历到 i(包含"整组 i 人")。
⚠️
初值不当:分值非负时初值取 0 即可。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n²)
空间复杂度
O(n)
n 最大
1000
运算量
约 5 × 10⁵

时间怎么算的?

空间都用在哪?

dp 数组 + 价值数组,都是 O(n)。

✅ 约 50 万次运算,瞬间完成。若 n 放大到 10⁵,就需要更高级的优化(本题不需要)。

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

🔗 常用技巧小抄

// 整数划分型 DP 的通用骨架
dp[0] = 0;
for (int i = 1; i <= n; i++)
    for (int k = 1; k <= i; k++)            // 枚举"最后一块"的大小
        dp[i] = max(dp[i], dp[i - k] + a[k]);

// 与背包问题的对照
// - 本题:dp[i] 表示"凑出总量 i"的最优值,k 可重复使用 -> 完全背包
// - 若题目改成"每种组大小最多用一次" -> 0/1 背包(外层变成枚举物品)
// 差别只在"循环顺序"和"物品是否可重复"

// 完全背包(本题形式)
for (int i = 1; i <= n; i++)
    for (int k = 1; k <= i; k++) dp[i] = max(dp[i], dp[i-k] + a[k]);

// 类似题目
// - 把 n 拆成若干正整数之和,使某种收益最大
// - 找零钱问题(硬币面额可重复使用)
// - 分段问题(每段长度有不同收益)

🌟 举一反三

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

能力点本题怎么用还能迁移到
整数划分 DP枚举"最后一块"的大小所有"把 n 拆成若干份"的问题
完全背包物品可重复使用找零钱、分组、切分
0/1 vs 完全看循环顺序与物品是否可重复背包问题的关键区分点
🌟
思考题:如果题目改成"每种组大小最多使用一次"(例如已经有 3 个组了就不能再建 3 人组),DP 要怎么改?(提示:那就变成0/1 背包了——需要增加一维"已经用了几个组",或者把物品(组大小)提到外层循环。"物品能否重复使用"是背包类问题最重要的区分点。)