专栏文章

题解：P11452 [USACO24DEC] Cake Game S

llalaji2010
P11452题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqepx8g
此快照首次捕获于
2025/12/04 03:35
3 个月前
此快照最后确认于
2025/12/04 03:35
3 个月前
查看原文

P11452 [USACO24DEC] Cake Game S

分析

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

AC CODE

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...