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

题目简化

我们需要将一个整数

n

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

解题思路

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

40

。

DFS 思路就是一个一个取，直到人数达到

n

就去取讨论积极度最大值。

CPP

#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

。

代码

CPP

#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)

其他方案

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

CPP

#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)

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

文章操作

题目简化

解题思路

优化

代码

其他方案

相关推荐

评论

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