G7018 [GESP202512 七级] 学习小组 题解

知识点：动态规划、贪心、排序、分段。

解题思路

排序积极度c。枚举大小至少2的组数k，最大奖励为最大k个c之和减最小k个c之和；DP按总人数s与非单人组数k，求组大小基础收益的最大和，再加奖励取最大。

为什么正确

每个非单人组最多贡献一个最大值与一个最小值，选两端k人分别作组极值可达到上界；其余成员任意分配，组大小用DP穷尽。

易错点

单人组的极差是0，不占k；k最多n/2，不能强制每组恰好两人。

复杂度

时间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<long long>c(n),a(n+1);
    for(auto &x:c)cin>>x;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(c.begin(),c.end());
    vector<vector<long long>>dp(n+1,vector<long long>(n+1,-(1LL<<60)));
    dp[0][0]=0;
    for(int s=1;s<=n;s++)for(int k=0;k<=s/2;k++) {
        dp[s][k]=dp[s-1][k]+a[1];
        for(int len=2;len<=s&&k;len++)dp[s][k]=max(dp[s][k],dp[s-len][k-1]+a[len]);
    }
    long long ans=0,gain=0;
    for(int k=0;k<=n/2;k++) {
        if(k)gain+=c[n-k]-c[k-1];
        ans=max(ans,dp[n][k]+gain);
    }
    cout<<ans;
}

说明

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