不会结论做个鬼系列
题意其实是在头尾(最多)两个栈以及中间一些双端队列依次取数,然后每个人都要最大化自己的价值
有一个结论,如果一段序列中,出现了三个相邻位置\(A,B,C\),满足\(A\le B\ge C\),那么可以把这三个数替换成\(A-B+C\).原因是假设先手某一次要取\(A\)(要取\(C\)同理),显然如果要取\(A\)说明此时\(A\)是最优决策废话,然后后手后面一定会取\(B\),因为先手的最优决策都是\(A\)而不是其他的,那么后手选\(B\)一定不差,不然先手为什么不选别的呢?同理,先手后面会取\(C\),如果不取\(C\)那他也不会白给后手一个\(B\)啊,所以这样取完三个数先手收益就是\(A-B+C\)
然后这样做完以后,所有栈/队列都会变成先递减然后递增的形式.对于队列,因为可以从两边取,那么每次只要取最大的就完事了,所以可以把所有队列元素放在一起排序,然后依次取;对于栈元素,从栈顶开始一直递减的那一段也是和队列一样的,但是递增的一段,显然先手一取,后手就会取下一个,导致先手亏,所以谁都不会先取,这一部分单独拎出来处理,即从栈底开始两两配对,把亏损的代价统计一下,然后放在最后面,看谁会取到
// luogu-judger-enable-o2
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double
using namespace std;
const int N=1e6+10;
const LL inf=1ll<<50;
LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,m,p[N][2];
LL a[N],sm,dd,st[N],tp,b[N],tb;
int main()
{
n=rd();
for(int i=1;i<=n;++i)
{
a[i]=rd();
sm+=a[i];
if(a[i])
{
if(!a[i-1]) p[++m][0]=i;
p[m][1]=i;
}
}
for(int i=1;i<=m;++i)
{
tp=0;
for(int j=p[i][0];j<=p[i][1];++j)
{
st[++tp]=a[j];
while(tp>=3&&st[tp-1]>=st[tp]&&st[tp-1]>=st[tp-2])
{
LL nw=st[tp]-st[tp-1]+st[tp-2];
--tp,--tp,--tp;
st[++tp]=nw;
}
}
if(i==1&&a[1])
{
int j=1;
for(;j+1<=tp&&st[j]>=st[j+1];) b[0]+=st[j+1]-st[j],++j,++j;
while(tp>=j) b[++tb]=st[tp--];
}
else if(i==m&&a[n])
{
for(int j=1;j<=tp/2;++j) swap(st[j],st[tp-j+1]);
int j=1;
for(;j+1<=tp&&st[j]>=st[j+1];) b[0]+=st[j+1]-st[j],++j,++j;
while(tp>=j) b[++tb]=st[tp--];
}
else
{
while(tp) b[++tb]=st[tp--];
}
}
sort(b+1,b+tb+1);
int ii=1;
while(~tb)
{
LL dt=b[tb--];
if(ii) dd+=dt;
else dd-=dt;
ii^=1;
}
printf("%lld %lld\n",(sm+dd)>>1,(sm-dd)>>1);
return 0;
}