CF1882C Card Game

某种程度上的抽卡游戏？

有这样一个结论：一个后缀中\([i+1,n]\) 中所有的正数都可以被取到，所以维护一个正数后缀和 \(s_i\)，枚举每个位置 \(i\)，如果 \(i\) 为奇数，答案对 \(a_i+s_{i+1}\) 取 \(\max\)，否则对 \(s_{i+1}\) 取 \(\max\)。

下面证明这个结论：先依次取掉 \([i+1,n]\) 中的奇数位置的正数，直到剩余正数稳定在偶数位置上，然后取掉 \(i\) 位置的数，之后依次取掉剩下的正数（已经变成奇数位置）。

下面是 AC 代码：

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    long long s = 0, ans = 0;
    for (int i = n; i >= 1; i--) {
        if (i & 1) {
            ans = max(ans, a[i] + s);
        } else {
            ans = max(ans, s);
        }
        if (a[i] > 0) {
            s += a[i];
        }
    }
    cout << ans << endl;
}

THE END