CF388C Fox and Card Game

题面

简化题意

$n$ 堆牌，两个人轮流取。A 只能取一堆牌的最顶上的牌，B 只能取最低下的。双方都想最大化取的牌的数字和。求最后双方的分数。

$n\leq 100,s_i\leq 100$，$s_i$ 是每堆牌的数量。

题解

优先考虑所有的 $s_i$ 都是偶数的情况。猜测出一个理想局面：A 拿走了每堆牌的上面一半；B 拿走了每堆牌的下面一半。

可以推出这样的局面是一定发生的。因为任意时刻一方做出一个不同于维持这个状态的决策时，另一方都可以进行一次操作恢复这个状态。如果这个局面对某一方不利，不利的这一方一定会把它调整为这个局面。这是这个题最有趣最重要的思想。

下面考虑奇数张牌的堆，显然只有中间那一张牌需要考虑，为先取这个牌堆的人先拿走。

于是直接贪心即可，奇数牌堆的情况每个人会根据其中间的那张牌的大小优先取大的去取。剩下的部分也是一半一半。

代码

#include<bits/stdc++.h>
#define int long long
#ifdef DEBUG
#   define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#   define debug
#endif
using namespace std;
bool Begin;
const int max_n=102;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(!isdigit(c)) w|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

int n,A,B;
priority_queue<int> q;

bool End;
#define File ""
signed main(){
    #ifndef ONLINE_JUDGE
    freopen(File ".in","r",stdin);
    freopen(File ".out","w",stdout);
    #endif
    debug("Memory : %lf\n",(&Begin-&End)/1024.0/1024);
    n=read();
    for(int i=1;i<=n;++i){
        int m=read();
        if(m&1){
            for(int i=1;i<=(m>>1);++i)
                A+=read();
            q.push(read());
            for(int i=1;i<=(m>>1);++i)
                B+=read();
        }
        else{
            for(int i=1;i<=(m>>1);++i)
                A+=read();
            for(int i=1;i<=(m>>1);++i)
                B+=read();
        }
    }
    bool op=1;
    for(bool op=1;!q.empty();op^=1,q.pop()){
        if(op)
            A+=q.top();
        else
            B+=q.top();
    }
    write(A),putchar(' '),write(B),putchar('\n');
    return 0;
}