题解：P13015 [GESP202506 六级] 学习小组

· · 题解

题目简化

我们需要将一个整数 n 划分为若干个正整数的和，每个正整数对应一个小组的人数。对于每一种划分方式，我们计算对应的积极度和，然后找出最大的那个。

解题思路

一眼看过去，DFS，容易超时，预计得分 40。

DFS 思路就是一个一个取，直到人数达到 n 就去取讨论积极度最大值。

#include <bits/stdc++.h>
using namespace std;
int a[1001];
int n;
int sum = INT_MIN;
void dfs(int j, int num)
{
    if (j == n)
    {
        sum = max(sum, num); // 取最大值
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if ((n - j) >= i)
            dfs(j + i, num + a[i]);
    }
}
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs(0, 0);
    cout << sum;
    return 0;
}

时间复杂度：\mathcal{O}(n^n)

优化

是时候上 DP 了！

仔细一看，这不就是完全背包嘛，不难看出，状态转移方程为：

dp_i = \max\big(dp_i,dp_{i - j} + a_j\big)

其中，a_j 为考虑总人数为 j，可以获得的讨论积极度值。 预计得分：100。

代码

#include <bits/stdc++.h>
using namespace std;
int a[1001];
int n;
int dp[1001] = {0};
int main(void)
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dp[0] = 0; // 初始化
    dp[1] = a[1];
    for (int i = 1; i <= n; i++)
    { // 遍历人数
        for (int j = 1; j <= i; j++)
        {                                                                                      // 遍历 a 数组，j  <= 人数，否则会越界
            dp[i] = max(dp[i], dp[i - /*因为第 i 项是从人数少 j 的那项转移而来的*/ j] + a[j]); // i 表示总人数 ,所以最后输出总人数为 n
        }
    }
    cout << dp[n];
    return 0;
}

时间复杂度：\mathcal{O}(n^2)

其他方案

此处还提供一个记忆化搜索的代码

#include<bits/stdc++.h>
using namespace std;
int a[1001];
int n;
int d[1001]; // 记忆数组，存储从位置 j 出发能得到的最大和
// 返回从位置 j 出发能得到的最大和
int dfs(int j) {
    // 如果已经到达终点，返回 0
    if(j == n) return 0;
    // 如果已经计算过，直接返回结果
    if(d[j] != -1) return d[j];
    int max_sum = 0;
    for(int i = 1; i <= n - j; i++) { // 小组大小 i 不能超过剩余学生数 n - j
        int c = dfs(j + i) + a[i];
        if(c > max_sum) {
            max_sum = c;
        }
    }
    // 存储讨论积极度
    d[j] = max_sum;
    return max_sum;
}

int main(void)
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    // 初始化记忆数组为 -1，表示未计算
    memset(d, -1, sizeof(d));
    int res = dfs(0);
    cout << res; 
    return 0;
}

时间复杂度也是：\mathcal{O}(n^2)