题解：P16882 [GKS 2022 #D] Maximum Gain

Sirius6699 · 2026-07-20 13:23:56 · 题解

P16882 Maximum Gain 题解

题目大意

给定两个数组 A 和 B，以及一个总答题数 K。每次可以从任意一个数组两端选择一个元素并得相应分数，之后该元素被移除。求最多能获得的总分数。

问题分析

对于一个数组，若要取出 t 个元素，得分必然等于从左端取 l 个与从右端取 r 个之和，且 l + r = t，因此可以预处理每个数组在取不同 t 时的最大得分，然后枚举两个数组之间的分配方案（从 A 取 x 个，从 B 取 K - x 个），取最大值即可。

具体实现

对于数组 A：

• 计算前缀和 \text{la}[i]：从左端取 i 个元素的和。
• 计算后缀和 \text{ra}[i]：从右端取 i 个元素的和。
• 枚举所有合法的 (l, r) 组合，且 l + r = t \le \min(N, K)。对于每个 t，记录 \max_{l+r=t}(\text{la}[l] + \text{ra}[r])，存入数组 \text{maxa}[t]。

同理处理数组 B 得到 \text{maxb}[t]。

最后合并两个数组的结果即可。

AC Code

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N=6005;
const int M=6005;
const int K=3005;

ll a[N],b[M];
ll la[N],ra[N];
ll lb[M],rb[M];
ll maxa[K],maxb[K];

void solve()
{
    int T;
    cin>>T;
    for(int cnt=1;cnt<=T;cnt++)
    {
        int n,m,k;
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i];
        cin>>m;
        for(int i=0;i<m;i++) cin>>b[i];
        cin>>k;
        la[0]=ra[0]=0;
        for(int i=1;i<=n;i++) la[i]=la[i-1]+a[i-1];
        for(int i=1;i<=n;i++) ra[i]=ra[i-1]+a[n-i];
        for(int i=0;i<=k;i++) maxa[i]=0;
        int lima=min(n,k);
        for(int l=0;l<=lima;l++)
        {
            int maxr=min(n-l,k-l);
            for(int r=0; r<=maxr;r++)
            {
                int t=l+r;
                maxa[t]=max(maxa[t],la[l]+ra[r]);
            }
        }
        lb[0]=rb[0]=0;
        for(int i=1;i<=m;i++) lb[i]=lb[i-1]+b[i-1];
        for(int i=1;i<=m;i++) rb[i]=rb[i-1]+b[m-i];
        for(int i=0;i<=k;i++) maxb[i]=0;
        int limb=min(m,k);
        for(int l=0; l<=limb;l++)
        {
            int maxr=min(m-l,k-l);
            for(int r=0; r<=maxr;r++)
            {
                int t=l+r;
                maxb[t]=max(maxb[t],lb[l]+rb[r]);
            }
        }
        ll ans=0;
        int maxx=min(n,k);
        for(int x=0;x<=maxx;x++)
        {
            int y=k-x;
            if(y>m) continue;
            ans=max(ans,maxa[x]+maxb[y]);
        }
        cout<<"Case #"<<cnt<<": "<<ans<<endl;
    }
}

signed main()
{
    solve();

    return 0;
}