【题目来源】
https://oj.czos.cn/p/4989
【题目描述】
班主任计划将班级里的 n 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。观察发现，如果一个学习小组中恰好包含 k 名同学，则该学习小组的讨论积极度为 ak。
给定讨论积极度 a1，a2， ...，an，请你计算将这 n 名同学划分为学习小组的所有可能方案中，讨论积极度之和的最大值。
【输入格式】
第一行，一个正整数 n，表示班级人数。
第二行，n 个非负整数 a1，a2，….，an，表示不同人数学习小组的讨论积极度。
【输出格式】
输出共一行，一个整数，表示所有划分方案中，学习小组讨论积极度之和的最大值。
【输入样例】
8
0 2 5 6 4 3 3 4
【输出样例】
12
【数据范围】
对于 40% 的测试点，保证 1≤n≤10。
对于所有测试点，保证 1≤n≤1000，0≤ai≤10^4。
【算法分析】
本题代码与“东方博宜OJ 6218：条形蛋糕 → https://blog.csdn.net/hnjzsyjyj/article/details/168774317”的代码一模一样。
【算法代码一：二维数组】
#include<bits/stdc++.h> using namespace std; const int N=1e4+5; int dp[N][N]; int main() { int n,val; cin>>n; for(int i=1; i<=n; i++) { cin>>val; for(int j=1; j<=n; j++) { if(j<i) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i][j-i]+val); } } cout<<dp[n][n]<<endl; return 0; } /* in: 8 0 2 5 6 4 3 3 4 out: 12 */【算法代码二：一维数组】
#include<bits/stdc++.h> using namespace std; const int N=1e4+5; int dp[N]; int main() { int n,val; cin>>n; for(int i=1; i<=n; i++) { cin>>val; for(int j=i; j<=n; j++) { dp[j]=max(dp[j],dp[j-i]+val); } } cout<<dp[n]<<endl; return 0; } /* in: 8 0 2 5 6 4 3 3 4 out: 12 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/168774317
https://blog.csdn.net/hnjzsyjyj/article/details/126126183
https://blog.csdn.net/hnjzsyjyj/article/details/159050238
