2025年6月GESP（C++六级）：学习小组
2025年6月GESP（C++六级）：学习小组
题目描述
班主任计划将班级里的 $ n $ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含 $ k $ 名同学，则该学习小组的讨论积极度为 $ a_k $。
给定讨论积极度 $ a_1, a_2, \ldots, a_n $，请你计算将这 $ n $ 名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。
输入格式
第一行，一个正整数 $ n $，表示班级人数。
第二行，$ n $ 个非负整数 $ a_1, a_2, \ldots, a_n $，表示不同人数学习小组的讨论积极度。
输出格式
输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。
输入输出样例 #1
输入 #1
4
1 5 6 3
输出 #1
10
输入输出样例 #2
输入 #2
8
0 2 5 6 4 3 3 4
输出 #2
12
说明/提示
对于 40%40\%40% 的测试点，保证 1≤n≤101\le n\le 101≤n≤10。
对于所有测试点，保证 1≤n≤10001\le n\le 10001≤n≤1000，0≤ai≤1040\le a_i\le 10^40≤ai≤104。
思路分析
- 问题目标：将n个同学划分为若干小组（小组人数任意），使得所有小组的积极度之和最大化。
- 核心思想：使用动态规划（DP）解决分组优化问题：
dp[j]表示将j个同学划分成若干小组能获得的最大积极度之和- 初始状态：
dp[0] = 0（0个同学的积极度为0）
- 状态转移：
- 对于每个小组人数
i（1≤i≤n） - 对于每个总人数
j（i≤j≤n） - 考虑划分出一个大小为
i的小组：剩余j-i个同学的最优解dp[j-i]加上当前小组的积极度a[i] - 通过
max()函数更新dp[j]，保留更优解
- 对于每个小组人数
- 关键理解：
- 内层循环顺序处理保证每个小组规模只使用一次（避免重复计数）
- 通过枚举所有可能的小组规模，覆盖所有划分方案
- 最终解存储在
dp[n]中，表示n个同学的最优划分结果
AC代码
#include<bits/stdc++.h>
using namespace std; int n;
int a[1010]; // 存储不同人数小组的积极度，a[i]表示人数为i的小组的积极度
int dp[1010]; // dp[j]表示将j个同学划分成若干小组能获得的最大积极度之和int main(){ cin >> n; // 输入班级总人数// 读取积极度数据，注意a[1]对应小组人数1的积极度，a[2]对应小组人数2的积极度，以此类推for(int i = 1; i <= n; i++) {cin >> a[i];}// 动态规划求解for(int i = 1; i <= n; i++) { // 枚举小组人数i（从1人到n人）for(int j = i; j <= n; j++) { // 枚举总人数j（从i开始，因为至少需要i人才能组成一个小组）// 状态转移方程：考虑将j个人划分出一个大小为i的小组// dp[j]可能由两种情况得到：// 1. 不划分i人小组：保持原值dp[j]// 2. 划分一个i人小组：剩余j-i人的最优解dp[j-i] + 当前i人小组的积极度a[i]dp[j] = max(dp[j], dp[j - i] + a[i]);}}cout << dp[n]; // 输出将n个同学划分的最大积极度之和return 0;
}
文末彩蛋：
点击查看老师的个人主页，学习csp信奥赛完整系列课程：
https://edu.csdn.net/lecturer/7901
