学习小组 I

班主任计划将班级里的 $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\%$ 的测试点，保证 $1\le n\le 10$。

对于所有测试点，保证 $1\le n\le 1000$，$0\le a_i\le 10^4$。

这是一道非常经典的动态规划（Dynamic Programming）入门题，属于“完全背包问题”的变种，即整数拆分（Integer Partition）最大化价值问题。

核心算法：动态规划

题目要求将 $n$ 个人分成若干小组，每组人数 $k$ 对应一个积极度 $a_k$。我们要让所有小组的积极度之和最大。

• 状态定义： 设 $dp[i]$ 表示将 $i$ 名同学划分为若干小组所能获得的最大积极度之和。

• 状态转移方程： 要计算 $dp[i]$，我们可以考虑：最后一次划分出来的那个小组有多少人（设为 $j$ 人，其中 $1 \le j \le i$）。那么此时的状态就是“前 $i-j$ 个人的最大积极度”加上“最后一个 $j$ 人小组的积极度”。

  $dp[i] = \max_{1 \le j \le i} \{ dp[i-j] + a_j \}$

• 边界条件： $dp[0] = 0$（0 个人时积极度为 0）。

与“完全背包问题”的对应关系

我们可以通过下表进行深入对比，理解其背后的算法模型：

从背包问题的视角看，我们实质上是有 $n$ 种物品（对应 $1$ 到 $n$ 人组），每种物品都有其重量 $j$ 和价值 $a_j$。由于我们可以组建任意多个同类型的小组，这与“每种物品数量无限”的完全背包模型完美契合。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    // a[j] 存储 j 人小组的积极度，数组下标从 1 开始
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // dp[i] 表示 i 个人能得到的最大积极度之和
    vector<long long> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) { // 计算 i 个人时的最优解
        for (int j = 1; j <= i; j++) { // 尝试最后一个小组的人数 j
            dp[i] = max(dp[i], dp[i - j] + a[j]);
        }
    }

    cout << dp[n] << endl;

    return 0;
}

复杂度分析

• 时间复杂度： 我们有两层嵌套循环，外层 $i$ 从 1 到 $n$，内层 $j$ 从 1 到 $i$。总计算量约为 $1 + 2 + \dots + n = \frac{n(n+1)}{2}$，即 $O(n^2)$。

  由于 $n \le 1000$， $n^2 = 10^6$，在 1 秒的运行时间内完全可以通过。

• 空间复杂度： 我们使用了一个大小为 $n+1$ 的数组，空间复杂度为 $O(n)$。