![题解：洛谷 P14922 [GESP202512 七级] 学习小组](http://pic.xiahunao.cn/yaotu/题解：洛谷 P14922 [GESP202512 七级] 学习小组)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14922 [GESP202512 七级] 学习小组 - 洛谷【题目描述】班主任计划将班级里的n nn名同学划分为若干个学习小组每名同学都需要分入某一个学习小组中。班级里的同学依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号第i ii名同学有其发言积极度c i c_ici。观察发现如果一个学习小组中恰好包含编号为p 1 , p 2 , … , p k p_1,p_2,\ldots,p_kp1,p2,…,pk的k kk名同学则该学习小组的基础讨论积极度为a k a_kak综合讨论积极度为a k max { c p 1 , c p 2 , … , c p k } − min { c p 1 , c p 2 , … , c p 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}\}akmax{cp1,cp2,…,cpk}−min{cp1,cp2,…,cpk}也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。给定基础讨论积极度a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1,a2,…,an请你计算将这n nn名同学划分为学习小组的所有可能方案中综合讨论积极度之和的最大值。【输入】第一行一个正整数n nn表示班级人数。第二行n nn个非负整数c 1 , c 2 , … , c n c_1,c_2,\ldots,c_nc1,c2,…,cn表示每位同学的发言积极度。第三行n nn个非负整数a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1,a2,…,an表示不同人数学习小组的基础讨论积极度。【输出】输出一行一个整数表示所有划分方案中学习小组综合讨论积极度之和的最大值。【输入样例】4 2 1 3 2 1 5 6 3【输出样例】12【算法标签】#普及plus【代码详解】// 55分版本#includebits/stdc.husingnamespacestd;constintN305;intn,c[N],a[N],dp[N];// n: 目标长度c: 输入数组但未使用a: 长度为i的区间的价值dp: 动态规划数组intmain(){cinn;// 输入目标长度nfor(inti1;in;i)cinc[i];// 输入数组c但在后面的代码中没有使用for(inti1;in;i)cina[i];// 输入长度为i的区间的价值a[i]// 完全背包问题用各种长度的区间组合成长度为n求最大总价值for(inti1;in;i)// 遍历每种区间长度ifor(intji;jn;j)// 遍历所有可能的长度jdp[j]max(dp[j],dp[j-i]a[i]);// 状态转移方程coutdp[n];// 输出组合成长度为n的最大价值return0;}#includebits/stdc.husingnamespacestd;constintN305;intn,c[N],a[N],dp[N][N];// n: 总长度c: 额外收益数组a: 区间价值数组dp: 动态规划数组intmain(){cinn;// 输入总长度nfor(inti1;in;i)cinc[i];// 输入额外收益数组cfor(inti1;in;i)cina[i];// 输入长度为i的区间的价值a[i]sort(c1,cn1);// 对c数组进行排序用于计算额外收益// 初始化不选择任何区间i0的情况for(inti1;in;i)dp[i][0]dp[i-1][0]a[1];// 全部用长度为1的区间填充累积价值// 动态规划for(inti2;in;i)// i: 当前区间长度for(intji;jn;j)// j: 当前总长度for(intk1;kj/2;k)// k: 选择的区间数量{// 状态转移从总长度为j-i已选k-1个区间转移过来// 加上当前长度为i的区间价值a[i]// 再加上额外收益最大的k个c值减去最小的k个c值dp[j][k]max(dp[j][k],dp[j-i][k-1]a[i](c[n-k1]-c[k]));}intans-1e9;// 初始化答案为负无穷for(inti0;in;i)// 遍历所有可能的区间数量ansmax(ans,dp[n][i]);// 更新最大价值coutansendl;// 输出结果return0;}【运行结果】4 2 1 3 2 1 5 6 3 12
题解：洛谷 P14922 [GESP202512 七级] 学习小组
发布时间：2026/5/18 20:44:12
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14922 [GESP202512 七级] 学习小组 - 洛谷【题目描述】班主任计划将班级里的n nn名同学划分为若干个学习小组每名同学都需要分入某一个学习小组中。班级里的同学依次以1 , 2 , … , n 1,2,\ldots,n1,2,…,n编号第i ii名同学有其发言积极度c i c_ici。观察发现如果一个学习小组中恰好包含编号为p 1 , p 2 , … , p k p_1,p_2,\ldots,p_kp1,p2,…,pk的k kk名同学则该学习小组的基础讨论积极度为a k a_kak综合讨论积极度为a k max { c p 1 , c p 2 , … , c p k } − min { c p 1 , c p 2 , … , c p 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}\}akmax{cp1,cp2,…,cpk}−min{cp1,cp2,…,cpk}也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。给定基础讨论积极度a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1,a2,…,an请你计算将这n nn名同学划分为学习小组的所有可能方案中综合讨论积极度之和的最大值。【输入】第一行一个正整数n nn表示班级人数。第二行n nn个非负整数c 1 , c 2 , … , c n c_1,c_2,\ldots,c_nc1,c2,…,cn表示每位同学的发言积极度。第三行n nn个非负整数a 1 , a 2 , … , a n a_1,a_2,\ldots,a_na1,a2,…,an表示不同人数学习小组的基础讨论积极度。【输出】输出一行一个整数表示所有划分方案中学习小组综合讨论积极度之和的最大值。【输入样例】4 2 1 3 2 1 5 6 3【输出样例】12【算法标签】#普及plus【代码详解】// 55分版本#includebits/stdc.husingnamespacestd;constintN305;intn,c[N],a[N],dp[N];// n: 目标长度c: 输入数组但未使用a: 长度为i的区间的价值dp: 动态规划数组intmain(){cinn;// 输入目标长度nfor(inti1;in;i)cinc[i];// 输入数组c但在后面的代码中没有使用for(inti1;in;i)cina[i];// 输入长度为i的区间的价值a[i]// 完全背包问题用各种长度的区间组合成长度为n求最大总价值for(inti1;in;i)// 遍历每种区间长度ifor(intji;jn;j)// 遍历所有可能的长度jdp[j]max(dp[j],dp[j-i]a[i]);// 状态转移方程coutdp[n];// 输出组合成长度为n的最大价值return0;}#includebits/stdc.husingnamespacestd;constintN305;intn,c[N],a[N],dp[N][N];// n: 总长度c: 额外收益数组a: 区间价值数组dp: 动态规划数组intmain(){cinn;// 输入总长度nfor(inti1;in;i)cinc[i];// 输入额外收益数组cfor(inti1;in;i)cina[i];// 输入长度为i的区间的价值a[i]sort(c1,cn1);// 对c数组进行排序用于计算额外收益// 初始化不选择任何区间i0的情况for(inti1;in;i)dp[i][0]dp[i-1][0]a[1];// 全部用长度为1的区间填充累积价值// 动态规划for(inti2;in;i)// i: 当前区间长度for(intji;jn;j)// j: 当前总长度for(intk1;kj/2;k)// k: 选择的区间数量{// 状态转移从总长度为j-i已选k-1个区间转移过来// 加上当前长度为i的区间价值a[i]// 再加上额外收益最大的k个c值减去最小的k个c值dp[j][k]max(dp[j][k],dp[j-i][k-1]a[i](c[n-k1]-c[k]));}intans-1e9;// 初始化答案为负无穷for(inti0;in;i)// 遍历所有可能的区间数量ansmax(ans,dp[n][i]);// 更新最大价值coutansendl;// 输出结果return0;}【运行结果】4 2 1 3 2 1 5 6 3 12
