当前位置：首页 > news >正文

题解：洛谷 P14922 [GESP202512 七级] 学习小组

news 2026/6/5 11:32:14

本文分享的必刷题目是从蓝桥云课、洛谷、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}\}ak+max{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

【输出样例】

【算法标签】

#普及plus

【代码详解】

// 55分版本#include<bits/stdc++.h>usingnamespacestd;constintN=305;intn,c[N],a[N],dp[N];// n: 目标长度，c: 输入数组但未使用，a: 长度为i的区间的价值，dp: 动态规划数组intmain(){cin>>n;// 输入目标长度nfor(inti=1;i<=n;i++)cin>>c[i];// 输入数组c，但在后面的代码中没有使用for(inti=1;i<=n;i++)cin>>a[i];// 输入长度为i的区间的价值a[i]// 完全背包问题：用各种长度的区间组合成长度为n，求最大总价值for(inti=1;i<=n;i++)// 遍历每种区间长度ifor(intj=i;j<=n;j++)// 遍历所有可能的长度jdp[j]=max(dp[j],dp[j-i]+a[i]);// 状态转移方程cout<<dp[n];// 输出组合成长度为n的最大价值return0;}

#include<bits/stdc++.h>usingnamespacestd;constintN=305;intn,c[N],a[N],dp[N][N];// n: 总长度，c: 额外收益数组，a: 区间价值数组，dp: 动态规划数组intmain(){cin>>n;// 输入总长度nfor(inti=1;i<=n;i++)cin>>c[i];// 输入额外收益数组cfor(inti=1;i<=n;i++)cin>>a[i];// 输入长度为i的区间的价值a[i]sort(c+1,c+n+1);// 对c数组进行排序，用于计算额外收益// 初始化：不选择任何区间（i=0）的情况for(inti=1;i<=n;i++)dp[i][0]=dp[i-1][0]+a[1];// 全部用长度为1的区间填充，累积价值// 动态规划for(inti=2;i<=n;i++)// i: 当前区间长度for(intj=i;j<=n;j++)// j: 当前总长度for(intk=1;k<=j/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-k+1]-c[k]));}intans=-1e9;// 初始化答案为负无穷for(inti=0;i<=n;i++)// 遍历所有可能的区间数量ans=max(ans,dp[n][i]);// 更新最大价值cout<<ans<<endl;// 输出结果return0;}