题解：P11452 [USACO24DEC] Cake Game S

lalaji2010 · 2025-01-24 09:12:43 · 题解

P11452 [USACO24DEC] Cake Game S

分析

首先，题目给出 n 为偶数。所以不用去考虑很复杂的奇数情况。

考虑 Elsie 的操作永远是从序列的两端选择，并且若 Bessie 进行最优操作。由于 a_i \geq 1，所以 Bessie 不会进行操作，使得 Elsie 吃到 Bessie 合成的蛋糕（其实能够看出，这个游戏的主导权完全在 Elsie，因为 Bessie 的操作完全是为了规避 Elsie 的拾取），所以我们考虑对具有主导权的 Elsie 进行贪心。易知 Elsie 的操作次数是 tim=\frac{n}{2}-1，所以 Elsie 的操作就被我们简化成了：给定一个长为 n 的序列，从开头和结尾的连续段总共选 tim 个的最大收益，记录前缀和并枚举 tim 对于开头和结尾的分配即可。

AC CODE

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n;
int a[500005],sum[500005];
int k1,k2;
signed main(){
    cin>>t;
    while(t--){
        k1=0,k2=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
        }
        int tim=n/2-1,mx=0;
        for(int i=0;i<=tim;i++){
            mx=max(mx,sum[i+0]+sum[n]-sum[n-tim+i]);
        }
        cout<<sum[n]-mx<<" "<<mx<<"\n";
    }
    return 0;
}