题解 P2734 【游戏 A Game】

Kinandra · 2019-07-27 16:18:16 · 题解

看了好像都是DP的做法, 我发一个贪心的做法, 目前还不会证明, 欢迎大家一起讨论证明(或证伪).

考虑剩3个数a_1, a_2, a_3且a_2>a_1,a_2>a_3, 那么先手能比后手多取到a_1+a_3-a_2, 我们于是我们将形如a_i>a_{i+1}, a_i>a_{i-1}的缩成一个数a_{i+1}+a_{i-1}-a_i,反复操作直到\exists j,s.t.\forall i<j,a_{i+1}< a_i且\forall i>j,a_{i-1}< a_{i},即函数变为以j为谷值点的单谷函数.

时间容易用栈做到\mathcal O(n).

#include <cstdio>
#include <iostream>
using namespace std;
int read();
int n;
int st[1000005], top;
long long sum = 0;
int main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int x = read();
        sum += x;
        st[++top] = x;
        while (top >= 3 && st[top - 1] >= st[top] && st[top - 1] >= st[top - 2])
            st[top - 2] = -(st[top - 1] - st[top] - st[top - 2]), top -= 2;
    }
    int l = 1, r = top;
    long long res = 0;
    while (l <= r) {
        if (st[l] > st[r])
            res += st[l++];
        else
            res += st[r--];
        if (l > r) break;
        if (st[l] > st[r])
            res -= st[l++];
        else
            res -= st[r--];
    }
    printf("%lld %lld\n", (res + sum) / 2, (sum - res) / 2);
    return 0;
}
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) f = (c == '-') ? -1 : f, c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return x * f;
}