G6015 [GESP202506 六级] 学习小组 题解

知识点：完全背包、动态规划、整数划分。

解题思路

令dp[i]为把i人分成若干小组的最大收益，枚举最后一个小组大小j，转移dp[i]=max(dp[i-j]+a[j])。

为什么正确

每种分组都有一个最后组大小，移除它后剩下的最优收益由较小状态给出，反向拼接又能构造对应方案。

易错点

组大小可重复使用，不能误当0-1背包；dp[0]=0表示没有剩余人数。

复杂度

时间O(n²)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<long long>dp(n+1);
    for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)dp[i]=max(dp[i],dp[i-j]+a[j]);
    cout<<dp[n];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。