原文鏈接www.rzrgm.cn/zhouzhendong/AGC026F.html

前言

太久沒有發博客了，前來水一發。

題解

不妨設先手是 A，后手是 B。定義 \(i\) 為奇數時，\(a_i\) 為"奇數位上的數"；\(i\) 為偶數時， \(a_i\) 為"偶數位上的數"。定義左、右兩端的數分別表示 \(a_1\) 和 \(a_n\)。

考慮第一步：

首先，如果 A 取了左右某一個端點，那么他必然能取走和他取的點奇偶性相同的所有點。

然后，我們考慮 A 取了一個中間點后會發生什么：如果這個點左邊和右邊的剩余點數都是奇數，那么無論 B 取左還是右，取完某一邊之后，問題規模縮小成另一邊的情況，A 一定還是先手；否則 B 就可以取剩余點數為偶數的那一邊，并成為先手。

考慮 n 為偶數的情況。

如果 A 取了一個中間點，那么一定有一邊剩余奇數個，一邊剩余偶數個。那么 B 一定先操作偶數個的那一邊，然后獲得奇數那一邊的先手權，然后取最優策略。那么 A 還不如直接取偶數那一邊的端點，這樣做不僅取到了前一種方案能取到的，而且讓 B 在另一邊沒有了先手選擇權，一定不劣于前一種方案。

所以，當 n 為偶數時，先手能取到的最大值為 max(奇數位之和, 偶數位之和) 。

n 為奇數的情況較為復雜。

但是同理，A 不會去取一個位于奇數位的數，這樣會導致兩邊剩余個數都為偶數，不如直接取兩端。

于是，n 為奇數時，A 只有兩種策略：

• 取端點，即拿走所有奇數位的數。
• 取某一個偶數位的數。此時，如果 B 取左邊，那么 A 會繼續獲得右邊的先手權；否則 A 獲得左邊的先手權。這個過程可以看作問題規模的縮小。

如果將第二種策略用二叉樹的形式表示出來，那么 B 一定會選擇某一個葉子，使得最終答案最小。

考慮先假設所有偶數位的貢獻都已被 A 收取，那么 A 在一個區間執行“取端點”操作得到的收益就是這個區間的奇數位之和減去偶數位之和（注意這里的兩端點一定都是奇數）。

我們要做的是找出一個葉子集合，使得對這些葉子“取端點”的收益的最小值盡量大。

考慮二分答案x，之后問題轉化為是否可以刪除某些偶數位上的數，使得剩下的序列中任意一個極大的連續段之和都不小于x。

考慮暴力DP，枚舉右端點，然后再暴力枚舉前一個劃分點。時間復雜度不可接受。

由于DP信息只有“能”和“不能”，所以我們可以考慮貪心，只保留“能”的點中前綴和最小的即可。

時間復雜度 \(O(n\log \sum a_i)\)。

代碼

#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=300005;
int n;
int a[N],s[N];
bool check(int x){
	int v=0;
	for (int i=1;i<n;i+=2)
		if (s[i]-v>=x)
			v=min(v,s[i+1]);
	return s[n]-v>=x;
}
int main(){
	n=read();
	For(i,1,n)
		a[i]=read();
	if (n%2==0){
		int s0=0,s1=0;
		For(i,1,n)
			if (i&1)
				s0+=a[i];
			else
				s1+=a[i];
		cout<<max(s0,s1)<<" "<<min(s0,s1)<<endl;
		return 0;
	}
	For(i,1,n)
		if (i&1)
			s[i]=s[i-1]+a[i];
		else
			s[i]=s[i-1]-a[i];
	int L=1,R=n*1000,mid,ans=L;
	while (L<=R){
		mid=(L+R)>>1;
		if (check(mid))
			L=mid+1,ans=mid;
		else
			R=mid-1;
	}
	For(i,1,n)
		if (i%2==0)
			ans+=a[i];
	int s=0;
	For(i,1,n)
		s+=a[i];
	cout<<ans<<" "<<s-ans<<endl;
    return 0;
}