自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 22:20:13，当前版本为作者最后更新于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;
}