P6377 [PA 2010] Termites

先考虑只有 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

即可。

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

CPP

#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;
}

P6377 [PA 2010] Termites

文章操作

相关推荐

评论

P6377 [PA 2010] Termites