Omkar and Circle

Created by LXC on Sat Jan 13 17:16:56 2024

https://codeforces.com/problemset/problem/1372/D

ranting: 2100

tag: brute force, dp, games, greedy

problem

题意：

给出 $n$ 个非负整数 $a_1,a_2,\cdots , a_n$ 排成一个圆圈，$n$ 一定是个奇数。

对于所有的 $2\le i \le n$ ，$a_{i-1}$ 与 $a_i$ 被认为是相邻的，$a_1$ 和 $a_n$ 也被认为是相邻的。

你有一种操作：在圆圈上选一个元素，将其替换为相邻两个元素的和，然后从圆圈中删除两个相邻的元素。重复这个操作直到圆圈中仅剩一个数字为止，我们称其为圈圈值。

问能达到的最大圈圈值为多少。

输入：

第一行包含一个奇数整数 $n$ $(1\le n \le 2\times 10^5)$ - 圆圈内初始的元素个数。

第二行包含 $n$ 个整数 $a_1 , a_2 , \cdots a_n$ $(0\le a_i \le 10^9)$

输出：

输出能达到的最大圈圈值。

solution

通过找规律，最多能选取(n+1)/2个元素。并且选取的元素除了一对外，其他均是间隔了一个元素。

形如$\cdots, a_{i-2}, a_{i-2}, a_{i}, a_{i+1}, a_{i+3}, a_{i+5}, \cdots$

我们将数组扩充一倍，以便处理循环的情况。然后求前缀和，在前缀和上做差，维护最小值。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
    int n;
    cin >> n;
    vector<ll> a(n*2+1), p(n*2+1);
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        a[i+n] = a[i];
    }
    for (int i=1; i<=2*n; i++) {
        if (i>=2) p[i] = p[i-2];
        p[i] += a[i];
    }
    ll ans = 0;
    for (int i=n; i<=2*n; i++) {
        ans = max(ans, p[i]-p[max(0, i-n-1)]);
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}