简答题 偏难
#20240

学习小组 时间限制:1 s,内存限制:512 MB 【问题描述】 班主任计划将班级里的 n 名同学划分为若干个学习小组,每名同学都需要分入某一个学习小组中。观察…

学习小组

时间限制:1 s,内存限制:512 MB

【问题描述】

班主任计划将班级里的 n 名同学划分为若干个学习小组,每名同学都需要分入某一个学习小组中。观察发现,如果一个学习小组中恰好包含 k 名同学,则该学习小组的讨论积极度为 ak。

给定讨论积极度 a1、a2、……、an,请你计算将这 n 名同学划分为学习小组的所有可能方案中,讨论积极度之和的最大值。

【输入描述】

第一行,一个正整数 n,表示班级人数。

第二行,n 个非负整数 a1、a2、……、an,表示不同人数学习小组的讨论积极度。

【输出描述】

输出共一行,一个整数,表示所有划分方案中,学习小组讨论积极度之和的最大值。

【样例输入1】

4
1 5 6 3

【样例输出1】

10

【样例输入2】

8
0 2 5 6 4 3 3 4

【样例输出2】

12

【数据范围】

对于40%测试点,保证 1 <= n <= 10。

对于所有测试点,保证 1 <= n <= 1000,0 <= ai <= 10000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; using namespace std; const int N = 1005; int n, a[N]; int main() { cin &gt;&gt; n;     for (int i = 1; i &lt;= n; i++) {      cin &gt;&gt; a[i];         for (int j = 1; j &lt; i; j++)             a[i] = max(a[i], a[j] + a[i - j]);     }     cout &lt;&lt; a[n] &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。