题解 P3210 【[HNOI2010]取石头游戏】

· · 题解

感谢巨捞YCB orz

部分内容来自GuessYCB博客

题目的意思是：给两个栈和一些双端队列，问先后手最优方案下的取值。

因为总价值已经确定，那么先手的目标是使得自己与对方的差值尽可能大，后手的目标时尽可能小

先看栈，栈的取值其实是固定了的。

对于每一个栈，如果是单调下降

例如左边的栈 若有ai<ai-1<ai-2

那么当前取先手一定不是最优

因为后手取到的ai一定大于ai-1

如果对于栈单调上升

那么当前取后手一定不是最优

对于没有单调关系的变化

如果是ai-1<ai>ai+1这种情况

那么此时的先手与后手的收益差其实是确定了的

先手先取旁边两个点中的一个，后手一定取中间最优

先手再取另外一个

这样的取法对于中间的队列可行，对于两边的栈也是可行的

那么我们可以将三个合并为一个

即anew=ai−1+ai+1−ai

这样把所有的上凸关系全部合并完之后，大概整个图长这个样子

每一块一定是开口向上的二次函数形状

对于中间的队列，最优一定可以立刻取到

为什么呢，因为两边最大中间最小，当前先手一定会取两边，而两边又是合法的

对于左右两个栈的靠近里面的段也是合法的情况

那么对于这些石头排序后贪心选就可以了

对于栈单调靠近外面的段，进行相邻两两配对

无法配对的靠内单项和之前的石头一起排序

这样保证是最优的

因为没有人愿意第一个开始选那两段

所以在中间全部选完后，判断奇偶性直接算贡献就好了

附代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define il inline
#define rg register
#define ll long long
#define ld long double
#define inf 2147483647000
#define mod 998244353
#define N 1000001
using namespace std;
ll n,op,Qcnt,Gcnt;
ll tot,now,fir,ans,w[N],Q[N],G[N];
ll A[N],Acnt,B[N],Bcnt;
il void re(rg int &x);
il void Re(rg ll &x);
int main(){
    Re(n),G[0]=-inf;
    for(rg int i=1;i<=n;++i)
        Re(w[i]),tot+=w[i];
    for(rg int i=1;i<=n;++i){
        if(w[i]){
            G[++Gcnt]=w[i],w[i]=0;
            if(Gcnt>=3)
                while(G[Gcnt]<=G[Gcnt-1]&&G[Gcnt-1]>=G[Gcnt-2]){
                    G[Gcnt-2]=G[Gcnt]+G[Gcnt-2]-G[Gcnt-1];
                    Gcnt-=2;
                    if(Gcnt<=2)break;
                }
        }
        else break;
    }
    for(op=Gcnt;op>=1;--op){
        if(G[op]>=G[op-1])
            Q[++Qcnt]=G[op];
        else break;
    }
    for(rg int i=1;i+1<=op;i+=2)
        A[++Acnt]+=G[i+1]-G[i];
    if(op&1)Q[++Qcnt]=G[op];
//预处理前面
    Gcnt=0;
    for(rg int i=n;i>=1;--i){
        if(w[i]){
            G[++Gcnt]=w[i],w[i]=0;
            if(Gcnt>=3)
                while(G[Gcnt]<=G[Gcnt-1]&&G[Gcnt-1]>=G[Gcnt-2]){
                    G[Gcnt-2]=G[Gcnt]+G[Gcnt-2]-G[Gcnt-1];
                    Gcnt-=2;
                    if(Gcnt<=2)break;
                }
        }
        else break;
    }
    for(op=Gcnt;op>=1;--op){
        if(G[op]>=G[op-1])
            Q[++Qcnt]=G[op];
        else break;
    }
    for(rg int i=1;i+1<=op;i+=2)
        B[++Bcnt]+=G[i+1]-G[i];
    if(op&1)Q[++Qcnt]=G[op];
//预处理后面
    Gcnt=0;
    for(rg int i=1;i<=n;++i){
        if(w[i]){
            G[++Gcnt]=w[i];
            if(Gcnt>=3)
                while(G[Gcnt]<=G[Gcnt-1]&&G[Gcnt-1]>=G[Gcnt-2]){
                    G[Gcnt-2]=G[Gcnt]+G[Gcnt-2]-G[Gcnt-1];
                    Gcnt-=2;
                    if(Gcnt<=2)break;
                }
        }
        else while(Gcnt)Q[++Qcnt]=G[Gcnt--];
    }
    sort(Q+1,Q+Qcnt+1),op=1;
    for(rg int i=Qcnt;i>=1;--i)
        ans+=op*Q[i],op*=-1;
    ll AA=0,BB=0;
    for(rg int i=1;i<=Acnt;++i)
        AA+=A[i];//,cout<<A[i]<<' ';
    for(rg int i=1;i<=Bcnt;++i)
        BB+=B[i];//,cout<<B[i]<<' ';
//  cout<<endl;
//  cout<<ans<<' '<<AA<<' '<<BB<<endl;
    if(Qcnt&1)ans-=(AA+BB);
    else ans+=(AA+BB);
    printf("%lld %lld\n",(tot+ans)>>1,(tot-ans)>>1);
    return 0;
}
il void re(rg int &x){
    x=0;rg int w=1;char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')w=-1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    x*=w;
}
il void Re(rg ll &x){
    x=0;rg int w=1;char c=getchar();
    while((c<'0'||c>'9')&&c!='-')c=getchar();
    if(c=='-')w=-1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    x*=w;
}