[HNOI2010] 取石头游戏
前言：
个人感觉这道题很有难度，很有思维，这种博弈方式也值得积累。
正文：
-
确定博弈：首先你得知道，很多博弈题目都是假的，可能是贪心啊什么的。这道题看起来是两个人都想要自己的得分更大，但是实际上为了让自己得分更大，就必须让对方在对方的回合中取的少一些。因此这肯定是博弈而非每次贪心只顾自己，取能取到的最大值。
-
思考模型：大多数博弈都有基础模型，由于这道题是很明显的那种“我可以死，但你要死得更惨”的题目。这种题目通常是设定一个值 \(val=a-b\)，在两轮游戏中，前者取得 \(a\)，后者取得 \(b\) 时，前者期望 \(val\) 越大越好，后者反之。
-
落实限制：找到模型后，我们看看取到一个值的限制，发现就像是在双端队列或者栈中取值（用零来分段，开口都是面向这个零的）。我们在一个双端队列中进行考虑。
-
分类讨论：我们对连续的三个元素进行考虑，总共有四种情况：递增，递减，先增后减，先减后增。（后文我们称一次情况为一个过程）我们这里的渐变方向都是由外到内的（后文也一样）。对于递增的话，我们肯定要放到后面选择，因为这时候先手选择了，后手肯定可以选择到比它大的这个数字的。递减的话，我肯定优先选择目前所有递减里面最大的。先减少后增加同上。
-
特殊性质：当我们分类讨论到先减少后增加的情况的话，你会发现后手肯定会选择中间的，先手肯定会选择左后两个。为什么会这样？如果当前先手发现选取最优秀的话，他会把这个选走。由于先增加后减少，所以当前对于后手而言，选取比上一次最优还优秀的点肯定是最佳的，所以他肯定会选择中间那个。虽然对于先手而言，此时选取剩下的那个不一定最优秀，那我要是现在选取到其他更优的决策点的话，就变成了其他情况了，最终你还是要选取到这个剩下的点（即使中间可能会穿插很多其他过程）。那么我们直接把这种情况压成一个点。于是乎，所有的双端队列和栈中不会出现任何先增加后减少的情况了。
-
扩展：当发现上面这个性质后，所有的三个元素的情况可以扩展到一整个双端队列或栈的情况了，还是按照上面那个规则贪心轮流选取即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') {
f = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int l[2000006], r[2000006];
int a[2000006];
bool iszeroo[2000006];
int n;
int sum = 0;
int s = 0;
int tot = 0;
int val = 0;
bool cmp(int x, int y) { return x > y; }
signed main() {
n = read();
iszeroo[0]=1;
for (int i = 1; i <= n; i++) {
a[i] = read();
sum += a[i];
if (a[i] == 0) {
iszeroo[i] = 1;
}
l[i] = i - 1;
r[i] = i + 1;
}
r[0] = 1;
l[n + 1] = n;
for (int i = 3; i <= n; i = r[i]) { //从位置i开始，尝试与前面的所有数字合并
//合并操作
while (!iszeroo[i] && !iszeroo[l[i]] && !iszeroo[l[l[i]]] && a[l[i]] >= a[l[l[i]]] && a[l[i]] >= a[i]) { //满足条件
// printf("test:%lld\n",i);
iszeroo[l[i]] = iszeroo[l[l[i]]] = 1; //删除这两个数字
a[i] = a[l[l[i]]] + a[i] - a[l[i]];
r[l[l[l[i]]]] = i; //上一个不参与合并数字的右端点为i
l[i] = l[l[l[i]]]; //左端点为上一个不参与合并的位置
}
}
int L = r[0], R = l[n + 1];
// L:第一个链表
// R:最后一个链表
while (a[L] >= a[r[L]] && !iszeroo[L] && !iszeroo[r[L]]) {
s += a[r[L]] - a[L];
L = r[r[L]];
}
while (a[R] >= a[l[R]] && !iszeroo[R] && !iszeroo[l[R]]) {
s += a[l[R]] - a[R];
R = l[l[R]];
}
//先处理两个栈，统计出最后贡献s
for (int i = L; i <= R; i = r[i]) {
if (!iszeroo[i]) {
a[++tot] = a[i];
}
}
//对中间所有有值的链表
sort(a + 1, a + tot + 1, cmp); //贪心，两者轮流从大到小选取
a[++tot] = s; //栈的东西放在最后
// printf("test:%lld\n",tot);
for (int i = 1; i <= tot; ++i) {
if (i & 1)
val += a[i];
else
val -= a[i];
}
printf("%lld %lld", (sum + val) / 2, (sum - val) / 2);
}