P6377 [PA 2010] Termites

251Sec · 2025-06-04 16:26:16 · 题解

先考虑只有 deque 的情况，注意到若存在 a_i\le a_{i+1} \ge a_{i+2} 这样的结构，那么先手若取了 a_i 后手一定取 a_{i+1}，然后先手一定取 a_{i+2}，于是把它们合成一个数 a_i+a_{i+2}-a_{i+1}。于是所有 deque 都是单谷的，此时最优策略就是取最大的可取的数。然后有两个栈的情况，只需要把它们拼起来并在中间加上一个 -\infty 即可。

所以为什么大家都在写链表？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e13;
int n;
ll a[1000005];
vector<ll> Comp(vector<ll> a) {
    vector<ll> b;
    for (ll x : a) {
        b.push_back(x);
        while (b.size() >= 3) {
            ll x = b[b.size() - 1], y = b[b.size() - 2], z = b[b.size() - 3];
            if (y >= x && y >= z) {
                for (int i = 0; i < 3; i++) b.pop_back();
                b.push_back(x + z - y);
            }
            else break;
        }
    }
    return b;
}
vector<ll> f;
void Add(vector<ll> a) {
    int i = 0, j = a.size() - 1;
    while (i <= j) {
        if (a[i] >= a[j]) f.push_back(a[i++]);
        else f.push_back(a[j--]);
    }
}
ll s;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", a + i), s += a[i];
    for (int i = 1, j; i <= n; ) {
        if (a[i]) { i++; continue; }
        j = i + 1;
        while (j <= n && a[j]) j++;
        if (j <= n) {
            vector<ll> b;
            for (int p = i + 1; p < j; p++) b.push_back(a[p]);
            Add(Comp(b));
        }
        i = j;
    }
    vector<ll> t;
    for (int i = n; i; i--) {
        if (!a[i]) break;
        t.push_back(a[i]);
    }
    reverse(t.begin(), t.end());
    t.push_back(-inf);
    for (int i = 1; i <= n; i++) {
        if (!a[i]) break;
        t.push_back(a[i]);
    }
    Add(Comp(t));
    sort(f.begin(), f.end(), greater<ll>());
    ll res = 0;
    for (int i = 0; i < f.size(); i++) res += ((i & 1) ? -1 : 1) * f[i];
    if (res < 0) res += inf;
    else res -= inf;
    printf("%lld %lld\n", (s + res) / 2, (s - res) / 2);
    return 0;
}