自动搬运

查看原文

来自洛谷，原作者为

	GreenMelon 请不要给我发接龙/陌生人发无意义内容，否则大概率会被二十倍还击+拉黑，已拉黑一人 | 初二小蒟蒻，欢迎踩爆

搬运于2025-08-24 23:17:36，当前版本为作者最后更新于2025-07-15 16:06:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有三种情况：

• 一只蜜蜂在最左侧，另一只蜜蜂在中间，蜂巢在最右侧。则第一只蜜蜂能采到的蜂蜜总数就是从 $a_2$ 到 $a_n$ 的总和减去 $a_i$（$i$ 为第二只蜜蜂起点所在位置），第二只蜜蜂能采到的蜂蜜总数为从 $a_{i+1}$ 到 $a_n$ 的总和。
• 一只蜜蜂在最右侧，另一只蜜蜂在中间，蜂巢在最左侧。与第一种情况同理，只是顺序不同；
• 一只蜜蜂在最左侧，另一只蜜蜂在最右侧，蜂巢在中间。则第一只蜜蜂能采到的蜂蜜总数为 $a_2$ 到 $a_i$ 的总和，第二只蜜蜂能采到的蜂蜜总数为 $a_i$ 到 $a_{n-1}$ 的总和

注意不要采集两只蜜蜂起点位置的蜂蜜。

答案就是两只蜜蜂能采到的蜂蜜总和的最大值。

由于 $n$ 比较大，求区间和就使用前缀和优化。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define mod 998244353
#define ll long long
int n, a[N], b[N], ans;
main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];//前缀和数组
	}
	for(int i=2;i<n;i++) ans=max(ans, (b[n]-b[1]-a[i])+(b[n]-b[i]));
	for(int i=2;i<n;i++) ans=max(ans, (b[n-1]-a[i])+b[i-1]);
	for(int i=2;i<n;i++) ans=max(ans, (b[i]-b[1])+(b[n-1]-b[i-1]));
	cout<<ans;
}